时间戳

首页 > 解决方案 > 如何确定以下算法的时间复杂度？

algorithm - 如何确定以下算法的时间复杂度？

问题描述

我明天有一个期中考试，很难理解以下时间复杂度问题。

1.

Algorithm foo(n)
     i←0
     j←0
     while i<n do {
         if j=i then j←j+1
         else if j=2i then i←n−j
         else {
             i←i+1
             j←j+1
         }
     }

这是 O(1)

2.

Algorithm foo(n)
     i←0
     j←0
     while i<n do {
         if i=k then {
             A[i]←k
             k←k+1
             i←1
         }
     }
     else i←i+1

这是 O(n^2)

所以基本上，我一直在解决这些类型的问题是找到执行恒定数量操作的算法部分。对于算法 1，这将是变量和循环内的内容：

C1：

i←0
j←0

C2：

if j=i then j←j+1
         else if j=2i then i←n−j
         else {
             i←i+1
             j←j+1

然后，我计算循环的迭代次数 n，并将其添加到公式中：

f(n) = C1+nC2 为 O(n)（错误答案）

我可以说我的问题是我错误地计算了这两个循环的迭代次数。如果有人可以让我知道我的思维过程是否完全错误和/或我应该如何计算循环迭代，那将不胜感激。

标签： algorithmtimewhile-looptime-complexitycomputer-science

解决方案

你是否实现了算法，只是看看会发生什么？你应该，如果你还没有。

示例 1

def bigo_one(n):
    print(f"n == {n}")
    i = 0
    j = 0
    while i<n:
        if j==i:
            j = j + 1
        elif j == 2 * i:
            i = n - j
        else:
            i = i + 1
            j = j + 1
        print(i, j)

bigo_one(10)
bigo_one(100)
bigo_one(1000)

输出：

n == 10
0 1
1 2
8 2
9 3
10 4
n == 100
0 1
1 2
98 2
99 3
100 4
n == 1000
0 1
1 2
998 2
999 3
1000 4

从输出中很容易看出总是发生的事情，与 n 无关：

  1. j 增加到 2
  2. 我跳到 n-2
  3. 我增加到 n

总是 5 步 -> O(1)

示例 2

def bigo_nsquare(n):
    print(f"n == {n}")
    i = 0
    j = 0
    while i<n:
        if j==i:
            j = j + 1
            i = 1
        else:
            i = i + 1
        print(i, j)
        
bigo_nsquare(2)
bigo_nsquare(4)
bigo_nsquare(10)

输出：

n == 2
1 1
1 2
2 2
n == 4
1 1
1 2
2 2
1 3
2 3
3 3
1 4
2 4
3 4
4 4
n == 10
1 1
1 2
2 2
1 3
2 3
[...]

该循环正在逐步通过方阵的下三角形，因此它具有 O(n²) 复杂度是合理的。

推荐阅读