时间复杂度计算

一 时间复杂度的概念 一般情况下，算法的基本 *** 作重复执行的次数是模块n的某一函数f(n),因此，算法的时间复杂度记做 T(n) = O(f(n))。

随着模块n的增大，算法执行的时间增长率f(n)的增长率成正比，所以f(n)越小，算法的时间复杂度越低，算法的效率越高。

时间复杂度是总运算次数表达式中受n的变化影响最大的那一项(不含系数) 举个简单的例子： 这个算法执行了 1 + n 次，如果n无限大，我们可以把前边的1忽略，也就是说这个算法执行了n次。

时间复杂度常用大O符号表示，这个算法的时间复杂度就是O(n)。

二 计算时间复杂度计算出基本 *** 作的执行次数T(n) 基本 *** 作即算法中的每条语句（以;号作为分割），语句的执行次数也叫做语句的频度。

在做算法分析时，一般默认为考虑最坏的情况。

计算出T(n)的数量级 求T(n)的数量级，只要将T(n)进行如下一些 *** 作： 忽略常量、低次幂和最高次幂的系数，令f(n)=T(n)的数量级。

用大O来表示时间复杂度 当n趋近于无穷大时，如果lim(T(n)/f(n))的值为不等于0的常数，则称f(n)是T(n)的同数量级函数。

记作T(n)=O(f(n))。

只保留最高阶项，最高阶项存在且不是1，则去除与这个项相乘的常数。

用一个例子来表明以上的步骤：第一步计算基本语句执行次数：T（n）= n^2+n^3； 第二步T（n）的同数量级，我们可以确定 n^3为T（n）的同数量级； 第三步用大O表示时间复杂度：T（n）=O（n^3)。

三 常见的时间复杂度最常见的多项式时间算法复杂度关系为：O(1) < O(logn) < O(n) < O(nlogn) < O(n2) < O(n3)指数时间算法复杂度关系为：O(2n) < O(n!)< O(nn)举个例子来说明上述的时间复杂度：56四 复杂情况的时间复杂度分析1.并列循环复杂度分析2.函数调用的复杂度分析 记住，只有可运行的语句才会增加时间复杂度，因此，上面方法里的内容除了循环之外，其余的可运行语句的复杂度都是O(1)。

所以printsum的时间复杂度 = for的O(n)+O(1) = 忽略常量 = O(n)五 空间复杂度 空间复杂度(Space Complexity)是对一个算法在运行过程中临时占用存储空间大小的量度，记做S(n)=O(f(n))。

比如直接插入排序的时间复杂度是O(n^2),空间复杂度是O(1) 。

而一般的递归算法就要有O(n)的空间复杂度了，因为每次递归都要存储返回信息。

例如关于O(1)的问题， O(1)是说数据规模和临时变量数目无关，并不是说仅仅定义一个临时变量。

举例：无论数据规模多大，我都定义100个变量，这就叫做数据规模和临时变量数目无关。

就是说空间复杂度是O(1)。