时间复杂度计算

1 大O表示法

1. 用常数1取代运行时间中所有常数 3->1 O(1)
2. 在修改运行次数函数中,只保留最高阶项 n³⁺²ⁿ2+5 -> O(n^3)
3. 如果在最高阶存在且不等于1,则去除这个项目相乘的常数 2n^3 -> n^3

2 时间复杂度术语

• 常数阶
• 线性阶
• 平方阶
• 对数阶
• 立方阶
• nlog阶
• 指数阶(不考虑) O(2^n)或者O(n!) 除非是非常小的n,否则会造成噩梦般的时间消耗. 这是一种不切实际的算法时间复杂度. 一般不考虑!

时间复杂度术语.jpg

3.1 常数阶时间复杂度 O(1)

//1+1+1 = 3 O(1)
void testSum1(int n){
    int sum = 0;                //执行1次
    sum = (1+n)*n/2;            //执行1次
    printf("testSum1:%d\n",sum);//执行1次
}


//1+1+1+1+1+1+1 = 7 O(1)
void testSum2(int n){
    int sum = 0;                //执行1次
    sum = (1+n)*n/2;            //执行1次
    sum = (1+n)*n/2;            //执行1次
    sum = (1+n)*n/2;            //执行1次
    sum = (1+n)*n/2;            //执行1次
    sum = (1+n)*n/2;            //执行1次
    printf("testSum2:%d\n",sum);//执行1次
    
}

//x=x+1; 执行1次
void add(int x){
    x = x+1;
}

3.2 线性阶时间复杂度 O(n)

//x=x+1; 执行n次 O(n)
void add2(int x,int n){
    for (int i = 0; i < n; i++) {
        x = x+1;
    }
}

//1+(n+1)+n+1 = 3+2n -> O(n)
void testSum3(int n){
    int i,sum = 0;               //执行1次
    for (i = 1; i <= n; i++) {   //执行n+1次
        sum += i;                //执行n次
    }
    printf("testSum3:%d\n",sum);  //执行1次
}

3.3 对数阶时间复杂度 O(logn)

/*2的x次方等于n x = log2n  ->O(logn)*/
void testA(int n){
    int count = 1;         //执行1次
    //n = 10
    while (count < n) {
        count = count * 2;
    }
}

3.4 平方阶时间复杂度 O(n^2)

//x=x+1; 执行n*n次 ->O(n^2)
void add3(int x,int n){
    for (int i = 0; i< n; i++) {
        for (int j = 0; j < n ; j++) {
            x=x+1;
        }
    }
}

//n+(n-1)+(n-2)+...+1 = n(n-1)/2 = n^2/2 + n/2 = O(n^2)
//sn = n(a1+an)/2
void testSum4(int n){
    int sum = 0;
    for(int i = 0; i < n;i++)
        for (int j = i; j < n; j++) {
            sum += j;
        }
    printf("textSum4:%d",sum);
    
}

//1+(n+1)+n(n+1)+n^2+n^2 = 2+3n^2+2n -> O(n^2)
void testSum5(int n){
    int i,j,x=0,sum = 0;           //执行1次
    for (i = 1; i <= n; i++) {     //执行n+1次
        for (j = 1; j <= n; j++) { //执行n(n+1)
            x++;                   //执行n*n次
            sum = sum + x;         //执行n*n次
        }
    }
    printf("testSum5:%d\n",sum);
}

3.5 立方阶时间复杂度 O(n^3)

void testB(int n){
    int sum = 1;                         //执行1次
    for (int i = 0; i < n; i++) {        //执行n次
        for (int j = 0 ; j < n; j++) {   //执行n*n次
            for (int k = 0; k < n; k++) {//执行n*n*n次
                sum = sum * 2;          //执行n*n*n次
            }
        }
    }
}

4 思考题

思考题.jpg

有兴趣的话，评论区留下你的答案， 共同探讨

---

空间复杂度计算

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

程序空间计算因素:

1. 寄存本身的指令
2. 常数
3. 变量
4. 输入
5. 对数据进行操作的辅助空间

• 在考量算法的空间复杂度,主要考虑算法执行时所需要的辅助空间.
  空间复杂度计算:

int main(int argc, const char * argv[]) {
    // insert code here...
    printf("Hello, World!\n");
   
    int n = 5;
    int a[10] = {1,2,3,4,5,6,7,8,9,10};
    
    //算法实现O(1)
    int temp;
    for(int i = 0; i < n/2 ; i++){
        temp = a[I];
        a[i] = a[n-i-1];
        a[n-i-1] = temp;
    }

    for(int i = 0;i < 10;i++)
    {
        printf("%d\n",a[I]);

    }
    
    //算法实现O(n)
    int b[10] = {0};
    for(int i = 0; i < n;i++){
        b[i] = a[n-i-1];
    }
    for(int i = 0; i < n; i++){
        a[i] = b[I];
    }
    for(int i = 0;i < 10;i++)
    {
        printf("%d\n",a[I]);
        
    }
    
    return 0;
}

科普算法.jpg