时间复杂度空间复杂度

时间复杂度

在计算机科学中，算法的时间复杂度是一个函数，它定量描述了该算法的运行时间。这是一个代表算法输入值的字符串的长度的函数。时间复杂度常用大O符号表述，不包括这个函数的低阶项和首项系数。使用这种方式时，时间复杂度可被称为是渐近的，亦即考察输入值大小趋近无穷时的情况。例如，如果一个算法对于任何大小为 n （必须比 n0 大）的输入，它至多需要 5n3 + 3n 的时间运行完毕，那么它的渐近时间复杂度是 O(n3)。
为了计算时间复杂度，我们通常会估计算法的操作单元数量，每个单元运行的时间都是相同的。因此，总运行时间和算法的操作单元数量最多相差一个常量系数。相同大小的不同输入值仍可能造成算法的运行时间不同，因此我们通常使用算法的最坏情况复杂度，记为 T(n)，定义为任何大小的输入n所需的最大运行时间。另一种较少使用的方法是平均情况复杂度，通常有特别指定才会使用。时间复杂度可以用函数 T(n)的自然特性加以分类。

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

"O"是数学符号，它的严格定义是"若T(n)和f(n)是定义在正整数集合上的两个函数，则T(n)=O(f(n))表示存在正的常数C和n0 ,使得当n≥n0时都满足0≤T(n)≤C?f(n)。"用容易理解的话说就是这两个函数当整型自变量n趋向于无穷大时，两者的比值是一个不等于0的常数。

根据定义，求解算法的时间复杂度的具体步骤是：

　　⑴ 找出算法中的基本语句；
　　算法中执行次数最多的那条语句就是基本语句，通常是最内层循环的循环体。
　　⑵ 计算基本语句的执行次数的数量级；
　　只需计算基本语句执行次数的数量级，这就意味着只要保证基本语句执行次数的函数中的最高次幂正确即可，可以忽略所有低次幂和最高次幂的系数。这样能够简化算法分析，并且使注意力集中在最重要的一点上：增长率。
　　⑶ 用大Ο记号表示算法的时间性能。
　　将基本语句执行次数的数量级放入大Ο记号中。

推导大O阶

如何推导大o阶呢？我们给出了下面 的推导方法：
1.用常数1取代运行时间中的所有加法常数。
2.在修改后的运行次数函数中，只保留最髙阶项。
3.如果最高阶项存在且不是1,则去除与这个项相乘的常数。

简化步骤为：

以上步骤可以简化为： 
1. 找到执行次数最多的语句 
2. 计算语句执行次数的数量级
3. 用大O来表示结果 

时间复杂度题目：

1、

var i = 0, s = 0;
while(s 

求解步骤为：

while里面执行次数最多即为基本语句，频度设为t，则 s = (1+2+3+....+t)/2,并且由循环终止条件s

 [参考资料]

算法时间复杂度的计算 [整理]

数据结构-算法-时间复杂度计算

算法的时间复杂度分析

算法时间复杂度计算

时间复杂度维基百科