渐进性分析（asymptomatic analysis)& 大O的数学定义&时间复杂度

红太狼 2022-04-04 10:38 221阅读 0赞

### 一、什么是渐进性分析？ ###

假设同一个任务，有2种算法， 如何去找出那个更好？

一个简单的办法——用两个程序实现这两种算法，然后输入不同的数据，在你电脑上运行这两个程序，看看那个需要的时间更少。 用这种方法分析算法，有很多问题。

1. 对一些输入，可能第一个性能更好；对另外一些，可能第二更好

2. 对一些输入，第一个算法在一台机器上表现更好，另外一个算法在其它的机器上更好。

渐进性分析是为解决上面算法分析中的问题。**根据输入规模来评估一个算法的性能，而不是测量实际运行时间。**

**通过输入规模的增加来计算算法需要的时间和空间的增长趋势。**

参考： [Analysis of Algorithms ][Analysis of Algorithms]

***Given two algorithms for a task, how do we find out which one is better?***  
One naive way of doing this is – implement both the algorithms and run the two programs on your computer for different inputs and see which one takes less time. There are many problems with this approach for analysis of algorithms.  
1) It might be possible that for some inputs, first algorithm performs better than the second. And for some inputs second performs better.  
2) It might also be possible that for some inputs, first algorithm perform better on one machine and the second works better on other machine for some other inputs

[Asymptotic Analysis][] is the big idea that handles above issues in analyzing algorithms. In Asymptotic Analysis, we evaluate the performance of an algorithm in terms of input size (we don’t measure the actual running time). We calculate, how does the time (or space) taken by an algorithm increases with the input size.

### 二、大O的数学定义 ###

大O符号（Big O notation）是用于描述函数渐进行为的数学符号。

它用另一个（通常更简单的）函数来描述一个函数[数量级][Link 1]的渐近上界。

准确的数学定义：

若T（n）和f（n）是定义在正整数集合上的两个函数，则存在正的常数C和n0，使得当n≥n0时，满足  0≤T（n）≤C\*f（n）

记为：      T（n）=O（f（n））

也就是当n→∞时，f(n)的函数值增长速度与T（n)的增长速度同阶。

### 三、时间复杂度 ###

时间复杂度描述了该算法的运行时间，可以通过算法中的基本操作的执行次数来度量，记作  T（n）。它是问题规模n的函数。

T（n）=O（f（n）），   n→∞时，f(n)的函数值增长速度与T（n)的增长速度同阶

可以用更简单的f（n）来分析算法的时间复杂度。即  O(f（n) 来表示其算法复杂度。

时间复杂度不仅依赖于问题的规模n,也取决于待输入数据的性质（如数据的初始状态，对输入数据已经有序，不同排序算法时间复杂度不一样）。

[Analysis of Algorithms]: https://www.geeksforgeeks.org/analysis-of-algorithms-set-1-asymptotic-analysis/
[Asymptotic Analysis]: http://en.wikipedia.org/wiki/Asymptotic_analysis
[Link 1]: https://baike.baidu.com/item/%E6%95%B0%E9%87%8F%E7%BA%A7/3289119