一.时间复杂度
一个算法中的语句执行次数称为语句频度或时间频度，记为T(n)。n称为问题的规模，当n不断变化时，时间频度T(n)也会不断变化。
一般情况下，算法中基本操作重复执行的次数，是问题规模 n 的某个函数，用T(n)表示。若有某个辅助函数f(n),使得当n趋近于无穷大时，T(n)/f(n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。记作T(n)=Ｏ(f(n)),称Ｏ(f(n)) 为算法的渐进时间复杂度。
时间频度不相同时，渐进时间复杂度Ｏ(f(n)) 有可能相同，
T(n)=n^2+3n+4与T(n)=4n^2+2n+1它们的频度不同，但时间复杂度相同，都为O(n^2)。
现在我们根据一些书本上和网络上对时间复杂度概念的描述进行一下总结：
T(n)，语句频度，时间频度，亦称为时间复杂度。
O(f(n))，渐进时间复杂度。
前者T(n)是某个算法的时间耗费，它是该算法所求解问题规模 n的函数，而后者O(f(n))是指当问题规模趋向无穷大时，该算法时间复杂度的数量级。当我们评价一个算法的时间性能时，主要标准就是算法的渐近时间复杂度O(f(n))，因此，在算法分析时，往往对两者不予区分，经常是将渐近时间复杂度T(n)=O(f(n))简称为时间复杂度，其中的f(n)一般是算法中频度最大的语句频度。
注意：算法中语句的频度不仅与问题规模有关，还与输入实例中各元素的取值相关。但是我们总是考虑在最坏的情况下的时间复杂度。以保证算法的运行时间不会比它更长。
简单的说，就是保留求出次数的最高次幂，并且把系数去掉。 如
T(n)=2n^2+n+1 =O(n^2)
二.常见的时间复杂度
在编码方法中，时间复杂度当然越小越优：
常数阶O(1)、对数阶O(log2n)或O(lbn)、线性阶O(n)、线性对数阶O(n*log2n)、
平方阶O(n^2)、立方阶O(n^3)、k次方阶O(n^k)、指数阶O(2^n)。
例子：计算 1 + 2 + 3 + 4 + ...... + 100。
常规算法，代码如下：
int main()
{
int i, sum = 0, n = 100; /* 执行1次 */
for( i = 1; i <= n; i++) /* 执行 n+1 次 */
{
sum = sum + i; /* 执行n次 */
//printf("%d \n", sum);
}
printf("%d", sum); /* 执行1次 */
}
上面代码的算法时间复杂度，我们把它记作： O(n)。
再来看看高斯的算法，代码如下：
int main()
{
int sum = 0, n = 100; /* 执行1次 */
sum = (1 + n) * n/2; /* 执行1次 */
printf("%d", sum); /* 执行1次 */
}
这个算法的时间复杂度记作 O(1)。
从感官上我们就不难看出，从算法的效率上看，O(1) < O(n) 的，所以高斯的算法更快，更优秀。
这也就难怪为什么每本算法书开篇都是拿高斯的这个例子来举例了。
三.时间复杂度的计算题
例1：
Temp=i;
i=j;
j=temp;
以上三条单个语句的频度均为1，该程序段的执行时间是一个与问题规模n无关的常数。算法的时间复杂度为常数阶，记作T(n)=O(1)。如果算法的执行时 间不随着问题规模n的增加而增长，即使算法中有上千条语句，其执行时间也不过是一个较大的常数。此类算法的时间复杂度是O(1)。
例2：
x=91;
y=100;
while(y>0)
if(x>100) {x=x-10;y--;}
else x++;
解答：
T(n)=O(1)， 这个程序看起来有点吓人，总共循环运行了1000次，但是我们看到n没有? 没。这段程序的运行是和n无关的，就算它再循环一万年，我们也不管他，只是一个常数阶的函数。
例3：
void test_(int n)
{
i = 1, k = 100;
while (i<n)
{
k = k + 1;
i += 2;
}
}
设for循环语句执行次数为T(n),则 i = 2T(n) + 1 <= n - 1,
即T(n) <= n/2 - 1 = O(n)
例4
int n = 8, count = 0;;
for(int i=1; i<=n; i = 2) {
count++;
}
好明显，i的值是以i=i2的速度变化（1，2，4，8...），则循环体的执行次数
是以2为底数，以n为真数的对数的解，即O(
)
例5
int n = 8, count = 0;;
for(int i=1; i<=n; i *= 2) {
for(int j=1; j<=n; j++) {
count++;
}
}
时间复杂度为
图片.png
例6
int n = 8, count = 0;;
for(int i=1; i<=n; i++) {
for(int j=1; j<=n; j++) {
count++;
}
}
时间复杂度为
下面的文章，会讲解常见算法的时间复杂度，记得关注。
网友评论