数据结构每日更新——第一天：算法

1.算法的特性：有穷性、确定性、可行性、输入、输出

2.算法的设计的要求：正确性、可读性、健壮性、高效率和低存储量需求

3.算法的度量方法：事后统计方法（不科学）、事前分析估算能力

4.算法时间复杂度

推导大O阶：

• 用参数1代替加法参数
• 在修改后的运行次数函数中，只保留最高阶项
• 如果最高阶存在且不是1，则除去与这个项相乘的常数

得到的结果就是大O阶

5.常数阶

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

时间复杂度为O(1)

6.线性阶

    int i;
    for(i=0;i<n;i++){
        printf("复杂度为O(1)的程序步骤！");
    }

时间复杂度为O(n)

7.平方阶

    int i,j;
    for(i=0;i<n;i++){
        for(j=0;j<n;j++){
            printf("复杂度为O(1)的程序步骤！");
        }
    }

时间复杂度为O(n^2)

第二种情况：

    int i,j;
    for(i=0;i<n;i++){
        for(j=i;j<n;j++){
            printf("复杂度为O(1)的程序步骤！");
        }
    }

这里i循环是n次，但是j循环里面逐渐减少。

i=1，j=n-1;i=2,j=n-2;......
可得到总执行次数为：n^2/2 + n/2
所以时间复杂度为O(n^2)

8.对数阶

    int count=1;
    while(count<n){
        count = count * 2;
        printf("复杂度为O(1)的程序步骤！");
    }

这里count每次乘以2，离n越来越近，有多少个2相乘后大于n，则会退出循环。由2^x=n得到x=log2(n)
时间复杂度为O(logn)

9.一般在没有特殊说明情况下，都是指定最坏时间复杂度

10.空间复杂度（不扩展，主要讲时间复杂度，以后再来看）

11.常见时间复杂度所耗时间排序：

O(1)<O(logn)<O(n)<O(nlogn)<O(n^2)