浅谈算法复杂度

时间复杂度

1. 时间频度

一个算法执行的时间

2.时间复杂度

n 称为事件规模， 当n不断发生变化时， 时间频度T(n)也会不断变化, 这种变化规律称之为时间复杂度

一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数，用T(n)表示，若有某个辅助函数f(n),存在一个正常数c使得fn*c>=T(n)恒成立。记作T(n)=O(f(n)),称O(f(n)) 为算法的渐进时间复杂度，简称时间复杂度。

空间复杂度

空间复杂度(Space Complexity)是对一个算法在运行过程中临时占用存储空间大小的量度

复杂度分析

通常一个算法的复杂度是由其输入量决定的，随着输入的增加，
复杂度随之变化.
为了降低算法复杂度，应当同时考虑到输入量，设计较好的算法

实际计算算法复杂度(以时间为标准)

删除影响不大的常数相

O(1)

int aFunc(void) {
    printf("Hello, World!\n");      //  需要执行 1 次
    return 0;       // 需要执行 1 次
}

//T(n) = 2  则复杂度为O(1)

O(n)

int aFunc(int n) {
    for(int i = 0; i<n; i++) {         // 需要执行 (n + 1) 次
        printf("Hello, World!\n");      // 需要执行 n 次
    }
    return 0;       // 需要执行 1 次
}

//T(n) = n+(n+1), 则O(n)

O(n^2)

void aFunc(int n) {
    // 第一部分时间复杂度为 O(n^2)
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            printf("Hello, World!\n");
        }
    }
    // 第二部分时间复杂度为 O(n)
    for(int j = 0; j < n; j++) {
        printf("Hello, World!\n");
    }
}

//T(n) = n + n*(n + 1) +  n*n + n+(n+1) ，则O(n^2)

含有判断的算法

void aFunc(int n) {
    if (n >= 0) {
        // 第一条路径时间复杂度为 O(n^2)
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                printf("输入数据大于等于零\n");
            }
        }
    } else {
        // 第二条路径时间复杂度为 O(n)
        for(int j = 0; j < n; j++) {
            printf("输入数据小于零\n");
        }
    }
}
//O(n^2) 和 O(n), 选取最大的O(n^2)

O(log(n))

void aFunc(int n) {
    for (int i = 2; i < n; i++) {
        i *= 2;   //执行次数 t^2 = n; 执行次数t =log(2)(n) 
        printf("%i\n", i);
    }
}
T(t) = log(2)(n) = log(2n) 则O(log(n))

O(2^n)

long aFunc(int n) {
    if (n <= 1) {
        return 1;
    } else {
        return aFunc(n - 1) + aFunc(n - 2);
    }
}
//T(n) = T(n - 1) + T(n - 2)， 通过归纳证明法可以证明，当 n >= 1 时 T(n) < (5/3)^n，同时当 n > 4 时 T(n) >= (3/2)^n。