algorithm - 找到模块化算法的Big-O

Question

i=1
while i <= n do:
   j=0
   k=i
   while k%3 == 0 do:
      k = k/3
      j++
   end

   print i, j
   i++
end

什么是给定算法的Big-O(我们如何展示我的工作)？ 这个算法输出什么//?

我的回答和做法

O(nlogn)。因为外循环运行线性时间为 O(n)，而内循环依赖于 O(logn)。

但是我不确定是不是logn。

当 n = 10 时，

ij
00
10
20
31
40
50
61
70
80
92
100 ( 10, 0)

当 n = 30

i j
1 0
2 0
3 1
4 0
5 0
6 1
7 0
8 0
9 2
10 0
11 0
12 1
13 0
14 0
15 1
16 0
17 0
18 2
19 0
20 0
21 1
22 0
23 0
24 1
25 0
26 0
27 3
28 0
29 0
30 1

Answer 1

请注意，从 1 到 n 系列中的每三个数字都可以被 3 整除。在最坏的情况下，这样的数字最终会被 3 整除在 k 循环 log_3(i) 次。因此，该序列在三分之二的时间里表现得像O(n)，在三分之一的时候像O(n*log3(n))。因此，我们可以声称您的代码的上限为 O(n*log3(n))，尽管存在比这更严格的界限。

代码将打印系列中的每个值 i 以及该数字的“三个深度”。 “三深度”是指我们能够将 i 除以 3 的次数。显然，对于不是 3 的倍数的 i 值，深度为 0。