关于时间复杂度的问题?

skystars
  • 59

只是举例啊, 一个函数之前运行时间是15s,我优化之后运行时间是10s,我问我同事,是不是说明时间复杂度减少了,他说这说明不了。是我对 时间复杂度有误解吗?

回复
阅读 337
3 个回答

时间复杂度的重点落在“复杂度”的“度”上,而非“时间”。

这是一个相对的度量衡,而不是一个绝对的物理值。

换句话说,只看执行次数,不看每次执行的时间。次数多的(即复杂度高)、但单次执行时间短,是有可能比次数少的(即复杂度低)、但单次执行时间长的总花费时长要更短,所以不能说谁执行总时长短谁复杂度就低。

时间复杂度不是一个具体的时间, 是指代码中, 基本语句的执行次数的和问题规模(输入数据的数量)的相关度.

要测试的话, 不应该测试执行时间, 而是应该测试函数中, 执行最多的语句的次数.

比如

void fn(int n) {
    for (int i = 0; i < n; i ++) {
       // 执行各种语句
       ...
       ...
       for (int j = 0; j < n; j ++) {
           sum += j; // 这条最内层语句执行的次数是 n^2,  时间复杂度就是O(n^2)
       }
   }
}

image.png
如题,算法复杂度描述的是一个算法随着输入规模,运行所需时间的变化趋势,跟具体的时间并不挂钩

你知道吗?

宣传栏