image.png
首先我们要认识到，一个算法的运行是一步一步执行下去的过程(step by step procedure).
算法的执行有两个特点：1.未解决问题而执行2.执行时间是有限的
在不同规模(scale)的输入量下，算法的表现可能差异很大。
image
而对于一个算法，找到他的平均运行时间是一个非常难的事，我们往往更注意他的最坏情况(worst case)
对于一个算法的度量，我们当然可以有最简单的经验主义做法(Emprical Analysis)
测量、描点、连线
image
但这样的经验主义也会出现问题，比方说x86和x64的机器，i7和i5的CPU, 低电压降频版的CPU和正常CPU...很多大大小小的因素都可能导致程序运行的经验时间有差异。
那么这样的时间就不是一个好的度量。
因此我们引入了理论时间(theoretical analysis)
image
在描述一个算法时，具体实现我们通常用伪代码(pseudocode)表示，但对这个算法的性能评价我们往往通过时间复杂度，结合空间复杂度就可以直观的了解到。
实际的度量方法我们先来看一个例子：
image
分析：
赋值 1
for循环 n+(n-1)
// for(int i=1;i<n;i++), 赋值 n-1 次，比较大小 n 次
for循环内的操作都要乘以n-1次
对于 if A[i]>currentMax 我有异议，我认为是 n-1次，但这不重要
currentMax赋值 1*(n-1)
return 1
最后算加法，这个例题的答案是O(5n-2)=O(n), 我的答案是O(4n-1)=O(n)
总结：循环体内是乘法，每一行代码时间复杂度是加法
时间复杂度是一个量级的概念，而不是具体的值，比如O(5n)的量级是n，因为这个时间复杂度函数内最高量级是变量n的一次方
通过这个逻辑，我们可以知道：
image.png
n^{2}+4n )=O( [图片上传失败...(image-9a5c5f-1544358446105)]
n^{2} )
每次我们只取最高阶作为量级，类似于750的量级是百位，99的量级是十位。
image
所以既不要系数，也不要低阶余部，这就是我们的时间复杂度。
网友评论