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);
 }

您将在间隔中拥有 x ，然后您将[sqrt(n)/2, sqrt(n)]执行下一个周期的 x 次迭代。第一个周期的复杂度为log(n)，因此总体复杂度是第二个周期定义的 sqrt(n) 的 theta（log(n)增长速度慢于sqrt(n)）。