关于时间复杂度的问题？

Question

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

Answer 1

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

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

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

Answer 2

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

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

比如

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)
       }
   }
}

Answer 3

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