函数的大 O 计算

Question

如何计算函数的 O？

我需要知道这个函数的O。（和每个循环）

int find_c(int n)
  int i,j,c
  for(i=n*n; i > 1; i=i/4) //O(logn)
    for(j=n*n; j > n/2; j--) //?
      c++
  for(i=c; i > 0; i--) //O(c)
    if(random(0...99) > 0) //O(1)
      for(j=n; j > 0; j--) //O(n)
        c++ //O(1)
    else
      for(j=400; j > 1; j--) //O(400)?
        c++ //O(1)
  return c

Answer 1

int find_c(int n)
  int i,j,c
  for(i=n*n; i > 1; i=i/4) //O(logn)
    for(j=n*n; j > n/2; j--) //O(n2)
      c++   //c = O(n2.logn)
  for(i=c; i > 0; i--) //O(n2.logn)
    if(random(0...99) > 0) //O(1)
      for(j=n; j > 0; j--) //O(n)
        c++ //O(1)  //c = O(n3logn)
    else
      for(j=400; j > 1; j--) //O(1)
        c++ //c = O(n2log2)
  return c

所以最后的答案是O(n^3.log n)

函数的大 O 计算

Big O calculation for a function

big-o

loops