algorithm - 计算时间复杂度(2 个简单算法)

Question

这里有两个算法(伪代码):

Alg1(n)
1.    int x = n
2.    int a = 0
3.    while(x > 1) do
3.1.    for i = 1 to x do
3.1.1       a = a + 1
3.2     x = x - n/5

Alg2(n)
1.    int x = n
2.    int a = 0
3.    while(x > 1) do
3.1.    for i = 1 to x do
3.1.1       a = a + 1
3.2     x = x/5

区别在于第 3.2 行。

时间复杂度:

• 算法 1:c + c +n*n*2c = 2c + 2cn² = 2c(n² + 1) = O(n²)
• 算法 2:c + c +n*n*2c = 2c + 2cn² = 2c(n² + 1) = O(n²)

我想知道计算是否正确。

谢谢!

Answer 1

不，恐怕你不正确。

在第一个算法中，行:

x = x - n/5

使 while 循环 O(1) - 它会运行五次，无论 n 有多大。 for 循环是 O(N)，因此总体上是 O(N)。

相比之下，在算法 2 中，x 减少为

x = x/5

作为 x = n 开始，这个 while 循环在 O(logN) 中运行。但是，内部 for 循环每次也减少为 logN。因此，您再次执行 n + n/5 + n/25 + ... 操作，时间为 O(N)。