时间戳

首页 > 解决方案 > 如何计算此代码段的复杂度？

time-complexity - 如何计算此代码段的复杂度？

问题描述

我无法计算这段代码的时间复杂度。

for(i=0;i<n;i++){
    for(j=i+1;j<n;j++){
        //statement
    }
}

需要帮忙。

标签： time-complexity

解决方案

让我们尝试计算操作。问题是哪些操作是相关的？时间复杂度通常用大哦符号（或其他渐近符号）表示，因为它隐藏了精确计数操作的难度。因此，任何常数都可以算作1。加法是4还是4​​0无关紧要，重要的是重复了多少次。最后，执行多少次statement。

那我们来数一数吧。外循环从 0 到 n，而内循环从 i+1 到 n。因此，当 i 为 0 时，内部循环执行 n-1 次迭代，当 i 为 1 时，内部循环执行 n-2 次迭代，依此类推，直到 i 为 n-1 并且内部循环不再执行。所以，我们有：

(n-1) + (n-2) + ... + 1 + 0

总共有 n 个术语。这个连续数之和有一个众所周知的公式：它是 (n-1)(n-2)/2。

展开上面的乘积，我们得到 1/2(n^2-3n+2)。O(1/2(n^2-3n+2)) 等价于 O(n^2)。

至于为什么一切都归结为 O(n^2)，渐近符号理论背后有很多内容，但在实践中，它归结为“big-oh 在多项式中保留最重要的项并丢弃系数”（很容易用 big-Oh 的定义证明）。

推荐阅读