最坏和最好情况的时间复杂度

Question

我需要帮助来理解以下代码示例的最坏和最佳情况下的时间复杂度。如果每行代码需要 X 时间，我如何将时间表示为函数 T(n)？

谢谢。

SORT(X)

    for i = 0 to X.length - 1
        
        for j = X.length downto i + 1
            
            if X[j] < X[j-1]
            
                change X[j] with X[j-1]

Answer 1

如评论中所述，最佳情况发生在所有 j、X[j] >= X[j - 1] 时，即您的列表 X 已按升序排序。最坏的情况发生在所有 j、X[j] < X[j - 1] 时，即您的列表 X 已经按降序排序。但是请注意，无论情况如何，我们都必须遍历循环并执行 if 语句。唯一不同的是交换操作，不会影响时间复杂度分析。

对于所有 i，我们从 X.length 迭代到 i+1。
对于 i = 0，从 X.length 迭代到 1：n 操作（假设 X 有 n 个元素。）
对于 i = 1，从 X.length 迭代到 2：n-1 操作
对于 i = 2，从 X.length 迭代到 2：n-2 操作
...
对于 i = X.length - 1，从 X.length 迭代到 X.length：1 操作
对操作数求和： n + n-1 + ... + 1 = (n+1) 。 (n) / 2

因此我们可以得出结论T(n) = n*(n+1)/2。两种情况 (worst-best) 的时间复杂度变为：O(n^2)。

最坏和最好情况的时间复杂度

Worst and best case time complexity

algorithm

performance

time-complexity