请教LC233. Number of Digit One时间复杂度

以下是我的暴力解code（超时），请问下这段code的时间复杂度是多少？

1. class Solution {
   
2.     public int countDigitOne(int n) {
   
3.         int res = 0;
   
4.         for (int i = 1; i <= n; i++) {
   
5.             res += countEach(i);
   
6.         }
   
7.         return res;
   
8.     }
   
9.     public int countEach(int x) {
   
10.         int count = 0;
    
11.         while (x != 0) {
    
12.             if (x % 10 == 1) {
    
13.                 count++;
    
14.             }
    
15.             x /= 10;
    
16.         }
    
17.         return count;
    
18.     }
    
19. }

复制代码

看 Solution Approach #1

countEach是O(log n), countDigitOne是O(log 1 + log 2 + ... + log n) = O(n log n). 相加这一步的严格证明可以用放缩法：

log 1 + ... + log n <= log n + ... + log n = n log n
log 1 + ... + log n = 1/2 ((log 1 + log n) + (log 2 + log (n-1)) + ... + (log n + log 1)) = 1/2 (log n + log 2(n-1) + ... + log n) >= 1/2 (log n + ... + log n) = 1/2 n log n

lswalker 发表于 2020-6-7 08:58
countEach是O(log n), countDigitOne是O(log 1 + log 2 + ... + log n) = O(n log n). 相加这一步的严格证 ...

谢谢解答！请问为什么countEach是O(logn)?

usr_opta 发表于 2020-6-7 08:54
看 Solution Approach #1

Solution Approach #1是转换成String做的，跟我的方法不一样

小水 发表于 2020-6-7 09:08
谢谢解答！请问为什么countEach是O(logn)?

你的while循环里面每次把x除10，所以总共要走log n次循环，然后每次循环里面是O(1)的操作。log的底数不重要，复杂度都是一样的。
Edit: 可能有点confusion，我这里的x和n指的是一个东西，就是countEach的input哈