什么是算法的时间复杂度？

Question

如题所述

Answer 1

时间复杂度是一个函数，它定量描述了该算法的运行时间。常见的时间复杂度有以下几种。
1，log(2)n，n，n log(2)n ，n的平方，n的三次方，2的n次方，n!

1指的是常数。即，无论算法的输入n是多大，都不会影响到算法的运行时间。这种是最优的算法。而n！（阶乘）是非常差的算法。当n变大时，算法所需的时间是不可接受的。

用通俗的话来描述，我们假设n=1所需的时间为1秒。那么当n = 10，000时。
O（1）的算法需要1秒执行完毕。
O（n）的算法需要10，000秒 ≈ 2.7小时 执行完毕。

O（n2）的算法需要100，000，000秒 ≈ 3.17年 执行完毕。
O（n！）的算法需要XXXXXXXX(系统的计算器已经算不出来了)。
可见算法的时间复杂度影响有多大。

所以O（1）和O（n）差了2.7小时，区别显而易见。