数据结构note（二）

发表于 分类于 ， Waline： 阅读次数： 本文字数： 1.2k 阅读时长 ≈ 1 分钟

算法复杂度的一些简单实例

  • Algorithm01

1
2
3
4
5
void Algorithm01(){
    int sum=0,n=100;
    sum=(1+n)*n/2;
    printf("%d\n",sum);
}

一共进行了三步，这是一个$\mathcal{O}(1)$的算法.

  • Algorithm02

1
2
3
4
5
6
void Algorithm02(int n){
    int i;
    for(i=0,i<n;i++){
    printf("%d\n",i);
    }
}

for循环的执行次数即为$n$，故复杂度为$\mathcal{O}(n)$.

  • Algorithm03

1
2
3
4
5
6
void Algorithm03(int n){
    int count=1;
    while(count<n){
        count=count*2;
    }
}

可以看到，要想把while语句走完，根据判断条件和循环节，需要$log_2n$次，忽略声明变量的常数次复杂度，可得复杂度为$\mathcal{O}(\log_2n)$.

  • Algorithm04

1
2
3
4
5
6
7
8
void Algorithm04(int n){
    int i,j;
    for(i=0;i<n;i++){
        for(j=i;j<n;j++){
            printf("%d\n",i+j);
        }
    }
}

外循环$i=0$时，内循环执行了$n$次；$i=1$时，内循环执行$n-1$次……故循环共执行了$n+(n-1)+…+1=\frac{n(n+1)}{2}$次，取最高次项，复杂度为$\mathcal{O}(n^2)$.

  • Algorithm05

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void function05(int n){
    int i;
    for(i=0;i<n;i++){
        printf("hello world!\n");
    }
}

void Algorithm05(int n){
    n++;
    function05(n);
    int i,j;
    for(i=0;i<n;i++){
        function05(n);
    }
    for(i=0;i<n;i++){
        for(j=i;j<n;j++){
            printf("hello world!\n")
        }
    }
}

在第二个函数里调用了function05函数，故在第二个函数中计算，有$1+n+n2+\frac{n(n+1)}{2}$次，也即复杂度为$\mathcal{O}(n2)$.