函数花费的时间越多意味着它的运行时复杂性越大？

Question

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

例如:

x=very large input

timer start
foo(x)
timer end

print time

因此,如果时间是0秒,那么这意味着foo在O(n)或更少时运行,如果计时器是30-60秒,那意味着运行时必须大于O(n)？

一般来说,函数需要花费更多时间,这意味着它的运行时复杂性更大吗？

Answer 1

运行时复杂性或渐近复杂性是apriori分析的一部分.简单来说,这些是代码的理论测量.

例如,

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

根据上述例子,

Apriori(在运行代码之前)分析说,它的运行时复杂性将是O(n),因为循环将被执行n-1次.

假设我们运行此代码,我们发现代码需要1分钟才能执行.然后我们可以总结下面的事情,

1. do() function is taking more time -- it is costly
2. Running complexity is O(n)

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

如果您的代码执行1秒或1小时并不重要,则运行时复杂性对于一段代码是固定的.时间在这个功能的某个地方被浪费了.

如果你编写一个简单的程序来在循环中打印1-n,这很简单.

对我们来说,只要你打印1-n,时间复杂度总是为O(n).但是如果您的打印命令需要3秒才能打印一个数字,那么您的程序执行时间很长,但并不意味着时间复杂度为O(n ^ 2).

我希望你现在清楚:)