02、数据结构与算法实战：数据结构和算法的复杂度-程序员快看-教程，程序员编程资料站

学习笔记——数据结构与算法（二）：数据结构和算法的复杂度

效率指的是算法的执行时间，算法执行的时间取决于：算法采用的策略、方案、编译产生的代码质量、问题的输入规模、己起执行指令的速度。因此，抛开硬件软件的问题，主要依赖于算法的好坏和输入规模。

定义：在进行算法分析时，语句总的执行次数T（n）是关于问题规模n的函数，进而分析T（n）随着n的变化情况而确定T（n）的数量级，记作T（n）=O（f（n）），它表示随问题规模n的增大，算法执行时间的增长率和f（n）的增长率相同，称作算法的渐近时间复杂度，简称为时间复杂度。

一般情况下，随着输入规模n的增大，T（n）增长最慢的算法为最优算法。

1、用常数1取代运行时间中的所有加法常数；
2、在修改后的运行次数函数中，只保留最高阶项；
3、如果最高阶项存在且不是1，则去除与这个项相乘的常数；
4、得到的最后结果就是大O阶；

一般含有非嵌套循环涉及线性阶，随着问题规模n的扩大，对应计算次数呈直线增长。
例如

int i ,n = 100 , sum = 0;
for( i =0 ; i < n ; i++)
{
sum - sum + i ;
}

时间复杂度为O（n）

嵌套的循环，两个嵌套就是O（n^2）
思考：如果是2n ^ 2+n/2呢，根据上述讲的方法，所以还是n^2

2^x= n，则x = log（2）n，所以复杂度为O（logn）。

例题

分析：n++——一次，第二行：n ^ 2,第一个for循环同上，第二个for循环是n（n+1）/2，也是同上。所以就是3n^2 + 1，所以还是O（n ^ 2）

算法分析时，例如随机数查找，有可能在第一个或者最后一个。
平均运行时间是期望的运行时间。
最坏运行时间是一种保证，提到的运行时间都是最坏情况的运行时间。

通过计算算法所需的存储空间实现，计算公式S（n） = O(f(n))，n为问题的规模。

通常，用时间复杂度来指运行时间的需求，用空间复杂度指空间需求。