Java - addDigitsメソッドのBig O？

Question

このコードの大きな部分は何ですか？私はO（logn）と思っています。なぜなら、それぞれの再帰は、= 10になるからです。そうでなければ、O（n）でなければなりません。これについての考えは？

P.S：宿題に関する質問ではなく、インタビューの改訂のみです。答えは歓迎されます。

public class Solution { 
    public int addDigits(int num) { 
     int sum = 0; 
     while (num > 0){ 
      sum += num % 10; 
      num /= 10; 
     } 
     if (sum < 10){ 
      return sum; 
     } 
     else{ 
      return addDigits(sum); 
     } 
    } 
} 

Answer 1

私はあなたが最初sumを計算するときO(logn)は最初whileループをカバーするためO(logn)は、正解ではないと思います。しかし、合計が10より大きい場合、あなたは新しいsumだから10よりも大きい場合O(log(sum)) +計算の別のラウンドでの計算の別のラウンド、やる：

• を最初の計算は
• LOGNです最初の合計は9 * lognより小さくなります（たとえば、最初の数値が4桁の場合は9999より小さくなるため、最初の合計は9 * 4未満になります）。したがって、2番目の計算は最大ログになります（9 * logn）+2番目の合計の計算
• 2番目の合計は9 * log（9 * logn）より小さくなるため、3番目の計算はlog（9 * log 3番目の合計の計算。
• だから上など

だから、最終的な値はO(logn + log(logn) + log(log(logn)) + ...)ように見える - それは時にログ（ログ（...（LOGN）...））= 0