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)、全体的な複雑さは 2 番目のサイクルで定義されているように sqrt(n) のシータです (log(n)は よりも遅くなりますsqrt(n))。