02趣味算法 --- 算法复杂性

14天阅读挑战赛
努力是为了不平庸~
算法学习有些时候是枯燥的，这一次，让我们先人一步，趣学算法！欢迎记录下你的那些努力时刻（算法学习知识点/算法题解/遇到的算法bug/等等），在分享的同时加深对于算法的理解，同时吸收他人的奇思妙想，一起见证技术er的成长~

首先看一道题目------求下列序列之和

        -1,1,-1,1,.....,(-1)^n

// 第一种算法
int sum1(int n){
    int sum=0;
    for(int i=1,i<=n;i++)
        sum+=pow(-1,i); 
    return sum;
}

// 算法2

int sum2(int n){
    int sum=0;
    if(n%2==0)
        sum=0;
    else
        sum=-1;
    return sum;
}

算法1需要运行n+1次，而算法2仅仅需要运行1次！

时间复杂性

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

        平均运行时间是所有情况中最有意义的，因为它是期望的运行时间。一般在没有特殊说明的情况下，都是指最坏时间复杂度。

• 1、推导大O阶方法

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

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

      3）如果最高价项存在且其系数不是1，则去除与这个项相乘的系数。

• 2、常数阶

        注意：不管这个常数是多少，我们都记作O(1)，而不能是O(3)、O(12)等其他任何数字。

• 3、线性阶

        分析算法的复杂度，关键就是要分析循环结构的运行情况。

•  4、对数阶

int count=1;
while(count<n)
{
    count=count*2;
}

        由于每次count乘以2之后，就距离n更近了一分。也就是说，有多少个2相乘后大于n，则会退出循环。由2^x=n得到x=log2(n)。所以时间复杂度为O(logn)。

• 5、平方阶

int i,j;
for(i=0;i<m;i++)
{
    for(j=0;j<n;j++)
        {

    }
}

        时间复杂度为O(mn)

空间复杂度

        算法的空间复杂度通过计算所需的存储空间实现，算法空间复杂度的计算公式记作：S(n)=O(f(n))，其中，n为问题的规模，f(n)为语句关于n所占存储空间的函数。

        一般情况下，一个程序在机器上运行时，除了需要存储程序本身的指令、常数、变量和输入数据外，还需要存储对数据操作的存储单元。若输入数据所占用空间只取决于问题本身，和算法无关，这样只需要分析该算法在实现时所需的辅助单元即可。若算法执行时所需的辅助空间相对于输入数据量而言是个常数，则称此算法为原地工作，空间复杂度为O(1)。

        当不用限定词地使用“复杂度”时，通常是指时间复杂度。