Question

算法复杂度的计算

Answer 1

同一个问题可以用不同的算法解决，而一个算法的质量优劣将会影响到算法甚至程序的运行效率。一个算法的好坏主要从时间复杂度和空间复杂度来计算。

    时间复杂度

    一个算法所耗费的时间实际上是不能算出来的，必须上机运行才能知道。但我们也不需要对每个算法都去进行测试，只需要知道哪个算法耗时多，哪个算法耗时少就可以了。一个算法花     费的时间与算法中语句执行的次数成正比，哪个算法中语句执行次数多，它花费时间就多。

    一个算法所耗费的时间=算法中每条语句的执行时间之和

    每条语句的执行时间=语句的执行次数(即频度)×语句执行一次所需时间

    一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数，用T(n)表示，若有某个辅助函数f(n),存在一个正常数c使得fn*c>=T(n)恒成立。记作T(n)=O(f(n)),称O(f(n)) 为算法的 渐进时间复杂度。

所以我们可以得出的结论是：算法执行时间可以用执行次数表示。

    空间复杂度

与时间复杂度类似，空间复杂度是指算法在计算机内执行时所需存储空间的度量。记作：

S(n)=O(f(n))

算法执行期间所需要的存储空间包括三个部分：

1.算法程序所占的空间；

2.输入的初始数据所占的存储空间；

3.算法执行过程中所需要的额外空间。

具体的例子可以参考 十分钟搞定时间复杂度

转自：https://github.com/cttin/cttin.github.io/issues/17