c - 时间复杂度 C

Question

void f(int n) {
 int x = n;
 while (x * x > n) {
   x /= 2;
   printf (“x cubed = %d\n”, x * x * x);
 }
 while (x > 0)
   x--;
 printf("hello %d\n", x);
}

我不明白他们是怎么得到的 TETA(sqrt(n)) 的复杂性 ......有人可以向我解释如何找到这个算法的复杂性的正式方式，以及其他类似的......？我需要制作跟踪表吗？
是否有任何网站提供有关算法和复杂性的示例？

10 倍很多!

Answer 1

当您退出第一个 while 循环时:

 while (x * x > n) {
   x /= 2;
   printf (“x cubed = %d\n”, x * x * x);
 }

您将在区间 [sqrt(n)/2, sqrt(n)] 中有 x然后执行下一个循环的 x 次迭代。第一个周期的复杂度为 log(n)因此，整体复杂度是由第二个循环定义的 sqrt(n) 的 theta( log(n) 比 sqrt(n) 增长慢)。