时间复杂度与空间复杂度

• 1.算法的复杂度：
• 2.时间复杂度：
• • 1.大O表示法：
  • 2.大O推导方法：
  • 3.一些常见的大O运行时间：
• 3.空间复杂度：
• 4.个别特殊举例：
• • 1.斐波那契数列的时间和空间复杂度
  • 2.二分法的时间复杂度和空间复杂度

1.算法的复杂度：

算法的时间复杂度和空间复杂度合称为算法的复杂度。

​ 时间复杂度： 时间复杂度是指执行算法所需要的计算工作量；

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

算法的复杂性体运行该算法时的计算机所需资源的多少上，计算机资源最重要的是时间和空间（即寄存器）资源，因此复杂度分为时间和空间复杂度。

2.时间复杂度：

一个算法花费的时间与算法中语句的执行次数成正比例，哪个算法中语句执行次数多，它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度，记为T(n)。

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

1.大O表示法：

用O( )来体现算法时间复杂度的记法，我们称之为大O表示法。

算法复杂度可以从最理想情况、平均情况和最坏情况三个角度来评估，由于平均情况大多和最坏情况持平，而且评估最坏情况也可以避免后顾之忧，因此一般情况下，我们设计算法时都要直接估算最坏情况的复杂度。大O表示法所表示的是一个算法在最糟糕情况下的运行时间。

2.大O推导方法：

1.用常数1来取代运行时间中所有加法常数。

2.修改后的运行次数函数中，只保留最高阶项

3.最高项除去其相乘的常数，得到的结果就是大O阶。

举例：

单个循环体情况：

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

多重循环体情况：

void Demo(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)。

多个事件复杂度情况：

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

3.一些常见的大O运行时间：

• O(log n)，对数时间，二分查找。
• O(n)，线性时间，简单查找。
• O(n logn)，快速排序——速度较快的排序算法。
• O(n²)，选择排序——速度较慢的排序算法。
• O(n!)，旅行商问题的解决方案——非常慢的算法。

3.空间复杂度：

一个程序的空间复杂度是指运行完一个程序所需内存的大小，利用程序的空间复杂度，可以对程序的运行所需要的内存多少有个预先估计。一个程序执行时除了需要存储空间和存储本身所使用的指令、常数、变量和输入数据外，还需要一些对数据进行操作的工作单元和存储一些为现实计算所需信息的辅助空间。程序执行时所需存储空间包括以下两部分。

（1）固定部分：这部分空间的大小与输入/输出的数据的个数多少、数值无关，主要包括指令空间（即代码空间）、数据空间（常量、简单变量）等所占的空间，这部分属于静态空间。

（2）可变空间：这部分空间的主要包括动态分配的空间，以及递归栈所需的空间等，这部分的空间大小与算法有关。一个算法所需的存储空间用f(n)表示。S(n)=O(f(n))，其中n为问题的规模，S(n)表示空间复杂度。

通常来说，只要算法不涉及到动态分配的空间以及递归、栈所需的空间，空间复杂度通常为0(1)。

4.个别特殊举例：

1.斐波那契数列的时间和空间复杂度

//递归情况下的斐波那契数列
    public static int Fib(int num){
        if (num==1||num==2){
            return num;
        }
        return Fib(num-2)+Fib(num-1);
    }

递归的时间复杂度是： 递归次数*每次递归中执行基本操作的次数，所以，时间复杂度是： O(2^N)。

递归的空间复杂度是： 递归的深度*每次递归所需的辅助空间的个数，所以，空间复杂度是：O(N)。

2.二分法的时间复杂度和空间复杂度

二分查找在最坏的情况下依次是n/2,n/4,n/8一直到1为止。
假设是x次，然后我们可以观察到分母是每次都乘以1/2，分子不变，所以可以列出下面等式：

n(1/2)^x = 1

通过计算得出x=log2N，即时间复杂度为O(log2N);

非递归：

public static int binarySearch(int[] arr,int toFind) {
        int left = 0;
        int right = arr.length-1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (arr[mid] < toFind) {
                left = mid + 1;
            }
            else if (arr[mid] > toFind) {
                right = mid - 1;
            }
            else {
                return mid;
            }
        }
        return -1;
    }

时间复杂度：循环的基本次数是log2N，所以，时间复杂度是O(log2N);

空间复杂度：由于辅助空间是常数级别的，所以，空间复杂度是O(1)。

递归：

public static int binarySearch(int srcArray[], int start, int end, int key) {
        int mid = (end - start) / 2 + start;
        if (srcArray[mid] == key) {
            return mid;
        }
        if (start >= end) {
            return -1;
        } else if (key > srcArray[mid]) {
            return binarySearch(srcArray, mid + 1, end, key);
        } else if (key < srcArray[mid]) {
            return binarySearch(srcArray, start, mid - 1, key);
        }
        return -1;
    }

递归的次数和深度都是log2N,每次所需要的辅助空间都是常数级别的：
时间复杂度 : O(log2N)
空间复杂度：O(log2N)