算法学习笔记1-时间复杂度&&选择排序&&冒泡排序

时间复杂度

概念

在一个算法上花费的时间

计算方法

1. 忽略常量，如果运行时间是常数量级，则用1表示
2. 忽略低次幂
3. 忽略高次幂系数

让我们来看几个例子

1.常数算法O(1)

int sumr=0;

2.线性算法O(N)

//输出一个数组中的所有元素
    for (int k = 0; k <lengt ; ++k) {
        printf("%d\t",array[k]);
    }

3.O(n^2)

    for(int i=0;i<lenght-1;i++){
        for(int j=0;j<lenght-1;j++){
            if(Array[j]<Array[j+1])swap(Array,j,j+1);
        }
    }

1. 折半查找O(logN)

//求1到10的累加和
int i = 0;
int sum=0;
while(i<=n){
    sum+=i;
}

额外空间复杂度

除去样本量外还需要都少额外辅助空间，这个空间即为额外空间复杂度

冒泡排序(BubbleSort)

时间复杂度O(n^2)

    void maxSelectSort(int Array[],int lenght){
        for(int i=0;i<lenght;i++){
            for(int j=i+1;j<lenght;j++){
                if(Array[i]<Array[j])swap(Array,i,j);
            }
        }
    }
    void minSelectSort(int Array[],int lenght){
        for(int i=0;i<lenght;i++){
            for(int j=i+1;j<lenght;j++){
                if(Array[i]>Array[j])swap(Array,i,j);
            }
        }
    }

选择排序(SelectSort)

时间复杂度O(n^2)

    void maxSelectSort(int Array[],int lenght){
        for(int i=0;i<lenght;i++){
            for(int j=i+1;j<lenght;j++){
                if(Array[i]<Array[j])swap(Array,i,j);
            }
        }
    }
    void minSelectSort(int Array[],int lenght){
        for(int i=0;i<lenght;i++){
            for(int j=i+1;j<lenght;j++){
                if(Array[i]>Array[j])swap(Array,i,j);
            }
        }
    }

插入排序(InsertionSort)

跟数据状况有关

最好情况：有序=》O(N)

最差情况：逆序=》O(N^2)

平均情况：O(n^2)(最差情况下的指标)

    void minInsertionSort(int Array[],int lenght){
        for(int i=1;i<lenght;i++){
            for(int j=i-1; j>=0 && Array[j]>Array[j+1];j--){
                swap(Array,j,j+1);
            }
        }
    }
    void maxInsertionSort(int Array[],int lenght){
        for(int i=1;i<lenght;i++){
            for(int j=i-1; j>=0 && Array[j]<Array[j+1];j--){
                swap(Array,j,j+1);
            }
        }
    }