算法复杂度和分析

首先需要了解几个入门的概念：

复杂度分析函数ƒ(n)=m，其中n代表输入数据的规模，m代表基本的操作数量，如ƒ(n)=2n^2+3n+1。
语句总的执行次数 T(n)是关于规模n的函数，分析 T(n)关于n随时间变化确定 T(n)的数量级，算法的时间就计作T(n)=O(f(n))，表示随着问题规模的增大，算法执行的增长率和f(n)的增长率相同，计作算法的渐进复杂度，简称时间复杂度，f(n) 是问题规模的某个函数。这种表示计作大O 记法。
算法分析中，关于规模的函数，我们只关心最高阶的指数，其系数和其他项包括常数项都不做考虑，如 $ƒ(n)=2n^2+3n+1$ ，只考虑n^2。
分析算法复杂度，关键是分析循环结构的运行情况。

1、推导大O阶方法

用常数1取代运行时间中的所有加法常数。

将修改后的运行次数函数中，只保留最高阶项。

如果最高阶存在且不为1，则去除这个项的常数系数，得到的结果就是大O阶表示。

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

相当于运行3次，ƒ(n)=3，任何数据执行都是3次，按照推导方法，将常数改为1，发现没有了最高项，就得到O(1)。

int i;
for( i =0;i < n; i++)
{
//O(1)的操作
}

总的复杂度得到为O(n)。

int count = 1;
while(count<n)
{
count = count*2;
//O(1)的操作
}

相当于多少次2乘之后大于n，结束循环， $2^x=n => x= log_2n$ ，计作 $O(logn)$

最常见的就是冒泡排序的复杂度，如下例子：

int i,j;
for(i = 0 ; i< n ; i++)
    for(j = 0; j<n ; j++){
        //swap O(1)
     }

相当于n^2次操作，复杂度O(n^2)，如果两次循环次数不同，可以看作是积数的复杂度计作O(m*n)，如下代码：

int i,j;
for(i = 0 ; i< m ; i++)
    for(j = 0; j<n ; j++){
        //swap O(1)
     }

int i,j;
for(i = 0; i< n;i++)
    for(j = i; j <n ; j++)
         //do O(1)

分析这种情况下，当i = 0时, 执行了n次...当i=n - 1时,执行了1次,所以总的次数为
$n+(n-1)+(n-2)+...+1 = \frac{n(n+1)}{2}=\frac{n^2}{2}+\frac{n}{2}$
最终得到 $n^2$ ,即 $O(n^2)$ 。

for(int i=1; i<=n; i *= 2) {  
        for(int j=1; j<=n; j++) {  
            count++;  
        }  
    }

第一个循环为 $log_2n$ ，第二个循环为 n，因此复杂度为 $O(nlog_2n)$

以上就是读书的简单笔记，可以看到分析算法的时间复杂度不算特别困难，关键是要分析清楚具体算法的逻辑。要注意的一点是偏向理论的东西会更加的注重规范和步骤，要保持逻辑的严谨和细密。

读书：《大话数据结构》算法

保护视力

最后编辑于：2018.11.07 13:38:09