时间复杂度

近日在研究算法数据结构相关的知识，学习到一个名词，时间复杂度，特来此记录下。

时间复杂度：先来看看《“大话数据结构》是怎么说的“在进行算法分析时，语句总的执行次数T(n)是关于问题规模n的函数，进而分析T(n)随n的变化情况并确定T(n)的数量级。算法的时间复杂度，也就是算法的时间量度，记作：T(n)=O(f(n))。它表示随问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同，称作算法的渐近时间复杂度，简称为时间复杂度。其中f(n)是问题规模n的某个函数。
这样用大写O( )来体现算法时间复杂度的记法，我们称之为大O记法。
一般情况下，随着n的增大，T(n)增长最慢的算法为最优算法。”
而我总结的是就是根据你输入的条件执行的次数。不知道这么说有没有什么问题，还望指正。

推导大O阶方法有三点：

1. 用常数1取代运行时间中的所有加法常数。
   我总结的就是固定的，可预知的，不与输入条件有关的执行语句就是为固定值1
2. 只保留最高阶项。
3. 去除与这个项相乘的常数。

常数级

int sum = 0,n = 100;      /* 执行一次 */
sum = (1 + n) * n / 2;    /* 执行一次 */
printf("%d", sum);        /* 执行一次 */

上诉代码中执行次数为3.

int sum = 0, n = 100;     /* 执行1次 */
sum = (1 + n) * n / 2;    /* 执行第1次 */
sum = (1 + n) * n / 2;    /* 执行第2次 */
sum = (1 + n) * n / 2;    /* 执行第3次 */
sum = (1 + n) * n / 2;    /* 执行第4次 */
sum = (1 + n) * n / 2;    /* 执行第5次 */
sum = (1 + n) * n / 2;    /* 执行第6次 */
sum = (1 + n) * n / 2;    /* 执行第7次 */
sum = (1 + n) * n / 2;    /* 执行第8次 */
sum = (1 + n) * n / 2;    /* 执行第9次 */
sum = (1 + n) * n / 2;    /* 执行第10次 */
printf("%d", sum);        /* 执行1次 */

这段代码的执行次数为12次。
不管写多少sum = (1 + n) * n / 2; 的重复代码，这个问题的执行次数都是可知的一个常数，与 n 的大小无关的，所以称之为具有O(1)的时间复杂度，又叫常数阶。

线性阶

int i;//执行1次
for (i = 0; i < n; i++)//n+1次
{
    /* 时间复杂度为O(1)的程序步骤序列 *///n 次
}

上述代码执行次数为1+n+1+n = 2n+2次。根据大O推导方法，去除相加常数和相乘的常数，可得这个算法的复杂度为O(n)。

对数阶

int count = 1;
while (count < n)
{
    count = count * 2;
    /* 时间复杂度为O(1)的程序步骤序列 */
}

在这个算法中，有多少个2相乘后大于n，则会退出循环。由2x=n得到x=log2n。所以这个循环的时间复杂度为O(logn)。

平方阶

int i, j;
for (i = 0; i < n; i++)
{
    for (j = 0; j < n; j++)
    {
        /* 时间复杂度为O(1)的程序步骤序列 */
    }
}

这段代码中，程序共需循环n*n 次，故这个循环的时间复杂度为O(n²)。

屏幕快照.png

像O(n³)开始，过大的n都会使得结果变得不现实。除非是很小的n值，否则哪怕n只是100，都是噩梦般的运行时间。所以这种不切实际的算法时间复杂度，一般我们都不去讨论它。