另一个大O符号question...What是下面代码的大O:
for (int i = n; i > 0; i = i / 2){
for (int j = 0; j < n; j++){
for (int k = 0; k < n; k++){
count++;
}
}
}
我的想法是:分解一下,我认为外部循环是O(log2(n)),那么每个内部循环都是O(n),这会导致O(n^2 * log2(n))问题#1,对吗?
问题#2:当组合嵌套循环时,它
下面列出的两种方法的大O时间复杂度是多少?
是方法1 O(log n²)还是O(log n)?
方法2是O(n²)还是别的什么?
public static void method1(int n) {
int k = 0;
for (int i = 1; i <= n; i = i*2)
for (int j = n; j > 1; j = j/2)
k++;
}
public static void method2(int n) {
for
We use Ө-notation to write worst case running time of insertion sort. But I’m not able to relate properties of Ө-notation with insertion sort, why Ө-notation is suitable to insertion sort. How does the insertion sort function f(n), lies between the c1*n^2 and c2*n^2 for all n>=n0.
作为Ө(n^2)的插入排序的运
我不知道如何计算这个算法的时间复杂度,我知道嵌套循环是O(n^2),但我不知道如何处理.insert(),我得出了错误的结论,它是O(n^2 + wrong ),但我知道我不能用大O来求和,任何帮助都将不胜感激。
for i in range(arr_len):
for j in range(arr_len):
if (i == arr[j]):
max_bin_heap.insert(//whatever) //O(log n)
这段代码的大O是什么?,我认为它是O(logn),因为每个递归,num得到/= 10,否则,它必须是O(n)。对此有什么想法吗?
不是家庭作业问题,只是面试的复习。所以答案是受欢迎的。
public class Solution {
public int addDigits(int num) {
int sum = 0;
while (num > 0){
sum += num % 10;
num /= 10;
}
if (sum < 10){
所以我刚刚完成了下面的大的O/时间复杂度的问题,但我不确定我的答案或我做它们的方式,如果你熟悉它,请检查我的答案并给我一些建议。因为当我做大O问题的循环时,我总是感到困惑
1)
For each item N
For each item N
For each item N
do some kind of processing
EndFor
EndFor
This one should be the easiest, O(n^3), but someone said it should be O(n)?
2)
For each it
我正在学习Big-O,虽然我开始理解一些东西,但我仍然不能正确地衡量算法的Big-O。我有一个代码:
int n = 10;
int count = 0;
int k = 0;
for (int i = 1; i < n; i++)
{
for (int p = 200; p > 2*i; p--)
{
int j = i;
while (j < n)
{
do
{
count++;
k = count * j;
} while (k > j);
各位,假设我有一个名为sortAndPrint(int[] array)的方法。在这个方法中,我有一个算法,它使用快速排序算法对array进行排序,然后打印array的所有元素。我的问题是,排序和打印这两个操作的总时间复杂度是O(n)还是O(n + logN)?提前感谢!
public void sortAndPrint(int[] array){
//Use Quicksort alrogithm to sort the array first
...........
...........
//Print all of the elements of the
下面的嵌套for循环的时间复杂度是多少?
编辑。我认为这个问题的答案取决于另一个问题,我不知道是否有一个“规范”的答案。
这个问题是,大O表达式中的n (如O(n)、O(n^2) )是显式地引用名为n的输入参数,还是指表示输入大小的通用值。
到目前为止,给出的一些答案似乎与这里给出的答案相矛盾:,如果可能的话,我希望得到一些更清晰的答案。
for i in range(n):
for j in range(m):
print(i, j) # Output statement occurs n * m times.
我在想O(n^2),因为每个循环都是O(n),但我想知
所以我很难理解Big O Notation,我正在寻找一些例子来更好地理解它。现在让我们看一下下面的代码: `public static void main(String[] args)` {
int N = 4;
int sum = 0;
for (int i = 1; i < N; i = i*2)
{
for (int j = 1; j < N; j++)
{
sum++;
我必须分析这个循环和其他循环,并使用Big-O表示法确定它的运行时间。
for ( int i = 0; i < n; i += 4 )
for ( int j = 0; j < n; j++ )
for ( int k = 1; k < j*j; k *= 2 )`
这是我到目前为止所知道的:
for ( int i = 0; i < n; i += 4 ) = n
for ( int j = 0; j < n; j++ ) = n
for ( int k = 1; k < j*j; k *= 2 ) = log^2 n
现在我
我对这段代码的时间复杂性和用来查找它的逻辑感到困惑。
void doit(int N) {
for (int k = 1; k < N; k *= 2) { <----I am guessing this runs O(logN)
for (int j = 1; j < k; j += 1) { <------I am not sure how this one works.
}
}
}
我已经试过用手把它写出来了。但是我还是不明白。
谢谢您抽时间见我。
编辑:
再加上一个问题。相同的概念,不同的格式。
void do
是大的哦(Log )吗?我怎样才能用求和来证明呢?
//Input: A positive decimal integer n
//Output: The number of binary digits in n’s binary representation
count ← 1
while n > 1 do
count ← count + 1
n ← ⌊n/2⌋
return count
我试图在堆排序算法中计算构建堆的运行时间
BUILD-HEAP(A)
heapsize := size(A);
for i := floor(heapsize/2) downto 1
do HEAPIFY(A, i);
end for
END
时间为什么是线性的基本思想是因为heapify的时间复杂性取决于它在堆中的位置。如果节点是叶节点(至少占节点的一半),则需要O(1)时间,而在根节点时则需要O(logn)时间。
通过解决以下问题可以证明O(n)时间:
我在这里所理解的是,O(h)对于每个节点来说是最坏的情况,所以height=ln n如果节点位于根中-