数値が3で割り切れるかどうかをチェックする最悪の場合の実行時間を確認します。

Question

数値の割り算を3でチェックするアルゴリズムを作成しました。まず入力Nが1桁の数字かどうかを確認します。 Nが1桁の数字でない場合、その桁の合計が計算され、Nに割り当てられます。外側のwhileループは、桁数nが1に等しくなるまで繰り返します。次に、Nの最終値が0,3,6または9であり、その場合Nは3で割り切れる。 N = 5432157、n = 7のとき、N = 5 + 4 + 3 + 2 + 1 + 5 + 7 = 27、n = 2のときN = 2 + 7 = 9、n = 1。したがって、外側のwhileループは3回繰り返します。最悪の場合の分析のため

#include <stdio.h> 
    main(){ 
     int N,n=0,rN,sum=0; 
     printf("Enter the number: "); 
     scanf("%d",&N); 
     rN=N; 
     while(n!=1){ 
      n=0; 
      sum=0; 
      while(N>0){ 
       sum+=N%10; 
       N/=10; 
       n++; 
      } 
      N=sum; 
     } 
     if(N==0||N==3||N==6||N==9){ 
      printf("\n%d is divisible by 3.",rN); 
     } 
     else{ 
      printf("\n%d is not divisible by 3.",rN); 
     } 
    }   

、Iは、Nのすべての数字が9に等しいと仮定している私は何を観察したことである数字nは11未満、外側の数のためのループ反復の最大一方3回。 nが11以上で10^11未満の場合、ループは最大4回繰り返されます。私は10^11以上のnに対していくつかのケースを試してみたところ、外側のループが5回反復することがわかりました。私はこの場合の一般的な公式を見つけることができませんでした。また、outer whileループの反復ごとにn（現在のNの値の桁数）回繰り返すinner whileループに対して、whileループの繰り返しごとにnはどのように減少するのですか？

Answer 1

注意深く観察した場合、（外側の）反復のそれぞれは、ステップ数がlog(N_current)になります。各ステップであなたの番号はlog(N)（または正確には9*log(N)）になります。

N_currentの数字が1桁になるまで、外側の繰り返しが続きます。

だからあなたの総複雑になります -

log(N) + log(log(N)) + log(log(log(N))) + ... + 1 ;  (1) 

反復回数がlog*Nだろう。

さて、私は（1）を低減する方法を知っていますならばおおよその上、各ステップはlog(N)であることを考慮していない、あなたは

O(log(N) * log*(N)) _{として複雑さを書くことができます（資本Oマインド）}