两个都不是很准确,虽然复杂度会影响到运算时间,却不能用运算时间来表示,更不能直接理解为基本运算的次数。
如果一段代码中没有循环,就是常量复杂度,不管在什么情况,它的运算时间是一个常数。
如果这段代码中有非嵌套的循环,那么它的复杂度为线性复杂度,运算时间是根据循环的次数线性增长。
如果这段代码中有循环嵌套,那么它的复杂度就是指数复杂度,运算时间是根据嵌套深度和循环次数呈指数增长。
这是一个简单的理解方式。
在同一机器上,CPU时钟是恒定的(理论),每条汇编指令执行的时间是一样的,所以从某种角度上看,运算时间和基本代码运行次数是一个概念,但它们不能直观的表现出一个算法的复杂度, 所以准确来说,这两个说法都不正确。
我认为准确的说应该是:一段代码的复杂度是该段代码的指令数和运行后的执行指令总数之间的一个函数,这个函数可以是常量的、线性的、指数的......