一个函数花费的时间越多，是不是意味着它的运行时复杂度就越大？

Question

通过计时器测试来验证代码的运行时复杂性是否明智？

例如：

x=very large input

timer start
foo(x)
timer end

print time

因此，如果时间为 0 秒，则意味着

foo

的运行时间为 O(n) 或更短，如果计时器为 30-60 秒，则意味着运行时间必须大于 O(n)？

一般来说，一个函数花费的时间越多，是否意味着它的运行时复杂度越大？

Answer 1

运行时复杂性或渐近复杂性是先验分析的一部分。简而言之，这些都是代码的理论度量。

例如，

function foo (){
    for (i=1;i++;i<n)
        do x;
}

根据上面的例子，

Apriori（运行代码之前）分析表明，其运行时复杂度将为 O(n)，因为循环将执行 n-1 次。

假设如果我们运行这段代码，我们发现代码执行需要 1 分钟。那么我们可以得出以下结论，

1. do() 函数需要更多时间——成本高昂
2. 运行复杂度为O(n)

运行复杂度的结论是基于数据结构和循环的。它们与实际运行时间无关。

无论您的代码执行时间为 1 秒还是 1 小时，都没关系，一段代码的运行时复杂性是固定的。时间在该函数的某个地方被浪费了。

如果你写一个简单的程序来循环打印 1-n 就很简单了。

对于我们来说，只要打印 1-n，时间复杂度就始终是 O(n)。但是如果你的打印命令需要 3 秒来打印一个数字，那么你的程序执行时间会很长，但这并不意味着时间复杂度是 O(n^2)。