时间复杂度和空间复杂度

时间复杂度：算法需要执行的运算次数。而不是计算程序需要的时间。

定义

一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数，用T(n)表示，若有某个辅助函数f(n)，使得T(n)/f(n)的极限值（当n趋近于无穷大时）为不等于零的常数，则称f(n)是T(n)的同数量级函数。记作T(n)=O(f(n))，称O(f(n)) 为算法的渐进时间复杂度，简称时间复杂度。

如何计算时间复杂度

1.先计算基本操作重复执行的次数T(n)。
2.寻找T(n)同数量级f(n),同数量级一般有以下：1，logn，n，nlogn ，n的平方，n的三次方，2的n次方，n!。
3.计算T(n)/f(n)求极限看是否为常数c，如果存在常数c，则时间复杂度为O(f(n))。

二分法的时间复杂度即推理过程

假设使用二分法从一个长度为N的序列中查找一个元素。
推理过程：

查找次数	待查询的元素数量
1	N/2
2	N/2^2
3	N/2^3
k	N/2^k

我们知道:N/2^k>=1,而且计算时间复杂度都是按最坏的情况计算，因此

N/2^k = 1 =>
2^k = N =>
k=log2N

所以二分法查找重复执行的次数T(n)为log2N.
根据时间复杂度的定义，存在常数c，使得T(n)/f(n)。这里我们假设f(n)=logN，
则c=log2N/logN=1/2，满足条件。所以二分法的时间复杂度为O(logN)。

时间复杂度中的log（n）底数到底是多少？
所以，这里的推导过程是对的，但是时间复杂度为不对，不应该是log2N，而应该是logN。

举例：算法执行次数为：T(n) = n^2，那么 f(n) = n^2， f(n) = n^3， f(n) = n^4都是成立的，但是因为第一个 f(n)/T(n) =1，其他都为0，不符合条件，所以我们说这个算法的复杂度是 O(n^2) 。

常见时间复杂度

1.常数项对函数的增长速度影响并不大，所以当 T(n) = c，c 为一个常数的时候，我们说这个算法的时间复杂度为 O(1)；如果 T(n) 不等于一个常数项时，直接将常数项省略。

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

T(n) = 2,它的时间复杂度就是：O(1)。
如果T(n) = n + 29,因为常数项可以省略，所以，它的时间复杂度为：O(n)。

2.对于多个循环，假设循环体的时间复杂度为 O(n)，各个循环的循环次数分别是a, b, c...，则这个循环的时间复杂度为 O(n×a×b×c...)。分析的时候应该由里向外分析这些循环。

void aFunc(int n) {
    for(int i = 0; i < n; i++) {         // 循环次数为 n
        for(int j = 0; j < n; j++) {       // 循环次数为 n
            printf("Hello, World!\n");      // 循环体时间复杂度为 O(1)
        }
    }
}

此时时间复杂度为 O(n × n × 1)，即 O(n^2)。
3.对于顺序执行的语句或者算法，总的时间复杂度等于其中最大的时间复杂度。

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");
    }
}

此时时间复杂度为 max(O(n^2), O(n))，即 O(n^2)。

4.对于条件判断语句，总的时间复杂度等于其中 时间复杂度最大的路径 的时间复杂度。

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");
        }
    }
}

此时时间复杂度为 max(O(n^2), O(n))，即 O(n^2)。

例子：

1.斐波那契数列实现一（递归算法）

long aFunc(int n) {
    if (n <= 1) {
        return 1;
    } else {
        return aFunc(n - 1) + aFunc(n - 2);
    }
}

显然运行次数，T(0) = T(1) = 1，同时 T(n) = T(n - 1) + T(n - 2) + 1，这里的 1 是其中的加法算一次执行。
显然 T(n) = T(n - 1) + T(n - 2) 是一个斐波那契数列，通过归纳证明法可以证明，当 n >= 1 时 T(n) < (5/3)^n，同时当 n > 4 时 T(n) >= (3/2)^n。
所以该方法的时间复杂度可以表示为 O((5/3)^n)，简化后为 O(2^n)。
空间复杂度：O(n)。
2.斐波那契数列实现二（迭代算法）
//斐波那契数列:[1,1,2,3,5,8,13,21,34,55]

int FeibonacciInteraction(int a, int b, int num) {
    int c = 0;
    if (num <=0 ) {
        return -1;
    }else if (num == 1) {
        return a;
    }else if (num == 2) {
        return b;
    }else{
        while (num -2) {
            c = a + b;
            a = b;
            b = c;
            num --;
        }
        return c;
    }
}

它的时间复杂度为：O(n)。
空间复杂度：O(1)。

4.二分法（迭代方法）

int BinarySearch(int arr[], int len, int num) {
    assert(arr);
    //arr:[1,2,3,4,5,6,7,8,9]
    int left = 0;
    int right = len - 1;
    int mid;
    while (left <= right) {
        //0 + 8 + 1 = 9
        //
        mid = left + (right - left) / 2;
        if (num > arr[mid]) {
            left = mid + 1;
        }else if (num < arr[mid]) {
            right = mid - 1;
        }else{
            return mid;
        }
    }
    return -1;
}

每次都是在原有内容进行二分，所以时间复杂度是O(logn)。
因为变量值创建一次，所以空间复杂度为O(1)。
5.二分法（递归）

int BinarySearchRecursion(int arr[5], int left, int right, int aim) {
    int mid = left + (right - left) / 2;
    if (left <= right) {
        if (aim < arr[mid]) {
            right = mid - 1;
            BinarySearchRecursion(arr, left, right, aim);
        }else if(arr[mid] < aim){
            left = mid + 1;
            BinarySearchRecursion(arr, left, right, aim);
        }else if (aim == arr[mid]) {
            return mid;
        }
    }
    return -1;
}

时间复杂度为：O(logn)。
每进行一次递归都会创建变量，所以空间复杂度为O(logn)。

6.进阶：

void aFunc(int n) {
    for (int i = 2; i < n; i++) {
        i *= 2;
        printf("%i\n", i);
    }
}

假设循环次数为 t，则循环条件满足 2^t < n。
可以得出，执行次数t = log(2)(n)，即 T(n) = log(2)(n)，可见时间复杂度为 O(log(2)(n))，即 O(log n)。这个不懂？？？？

空间复杂度

空间复杂度 ：对一个算法在运行过程中临时占用存储空间大小的量度。

计算方法

①忽略常数，用O(1)表示
②递归算法的空间复杂度=递归深度N*每次递归所要的辅助空间
③对于单线程来说，递归有运行时堆栈，求的是递归最深的那一次压栈所耗费的空间的个数，因为递归最深的那一次所耗费的空间足以容纳它所有递归过程。

例子

int a;
int b;
int c;
printf("%d %d %d \n",a,b,c);

它的空间复杂度O（n）=O（1）；

2.递归

int fun(int n,)
{
int k=10;
if（n==k)
return n;
else
return fun(++n);
}

递归实现，调用fun函数，每次都创建1个变量k。调用n次，空间复杂度O（n*1）=O（n)。

参考链接：
十分钟搞定时间复杂度
时间复杂度和空间复杂度的简单讲解