Question

时间复杂度的概念

Answer 1

时间复杂度就是用来方便开发者估算出程序的运行时间

我们该如何估计程序运行时间呢，我们通常会估计算法的操作单元数量，来代表程序消耗的时间， 这里我们默认CPU的每个单元运行消耗的时间都是相同的。

假设算法的问题规模为n，那么操作单元数量便用函数f(n)来表示

随着数据规模n的增大，算法执行时间的增长率和f(n)的增长率相同，这称作为算法的渐近时间复杂度，简称时间复杂度，记为 O(f(n))

但是在数据本来有序的情况下时间复杂度是O(n)，也就对于所有输入情况来说，最坏是O(n^2) 的时间复杂度，所以称插入排序的时间复杂度为O(n^2)

同样的同理我们在看一下快速排序，都知道快速排序是O(nlogn)，但是当数据已经有序情况下，快速排序的时间复杂度是O(n^2) 的，严格从大O的定义来讲，快速排序的时间复杂度应该是O(n^2)

但是我们依然说快速排序是O(nlogn)的时间复杂度，这个就是业内的一个默认规定，我们这里说的O 代表的就是一般情况，不是严格的上界