数据结构初阶1 时间复杂度和空间复杂度

本章重点

1. 算法效率
2. 时间复杂度
3. 空间复杂度
4. 常见时间复杂度以及复杂度OJ练习

1.算法效率

1.1 如何衡量一个算法的好坏

如何衡量一个算法的好坏呢？比如对于以下斐波那契数列：

long long Fib(int N)
{
if(N < 3)
return 1;return Fib(N-1) + Fib(N-2);
}

斐波那契数列的递归实现方式非常简洁，但简洁一定好吗？那该如何衡量其好与坏呢？

这种递归的斐波那契数列在计算大数字的时候不见得很好用。

这是因为其时间复杂度和空间复杂的原因：

1.2 算法的复杂度

算法在编写成可执行程序后，运行时需要耗费时间资源和空间(内存)资源 。因此衡量一个算法的好坏，一般是从时间和空间两个维度来衡量的，即时间复杂度和空间复杂度。

##blue##
🔵时间复杂度:主要衡量一个算法的运行快慢，
🔵空间复杂度:主要衡量一个算法运行所需要的额外空间。

在计算机发展的早期，计算机的存储容量很小。所以对空间复杂度很是在乎。但是经过计算机行业的迅速发展，计算机的存储容量已经达到了很高的程度。

所以我们如今已经不需要再特别关注一个算法的空间复杂度。

2.时间复杂度

2.1 时间复杂度的概念

时间复杂度的定义：在计算机科学中，算法的时间复杂度是一个函数(数学中的函数)，它定量描述了该算法的运行时间。

一个算法执行所耗费的时间，从理论上说，是不能算出来的，只有你把你的程序放在机器上跑起来，才能知道。但是我们需要每个算法都上机测试吗？是可以都上机测试，但是这很麻烦，所以才有了时间复杂度这个分析方式。一个算法所花费的时间与其中语句的执行次数成正比例，算法中的基本操作的执行次数，为算法的时间复杂度。

即：找到某条基本语句与问题规模N之间的数学表达式，就是算出了该算法的时间复杂度。

例如：

// 请计算一下Func1中++count语句总共执行了多少次？
void Func1(int N)
{int count = 0;for (int i = 0; i < N; ++i){for (int j = 0; j < N; ++j){++count;}}for (int k = 0; k < 2 * N; ++k){++count;}int M = 10;while (M--){++count;}printf("%d\n", count);
}

F(N)=N^2+2*N+10

N = 10 F(N) = 130
N = 100 F(N) = 10210
N = 1000 F(N) = 1002010

实际中我们计算时间复杂度时，我们其实并不一定要计算精确的执行次数，而只需要大概执行次数，那么这里我们使用大O的渐进表示法。

像上面的count次数来说，根据数据的慢慢变大N^2更能代表该段程序的时间复杂度

2.2 大O的渐进表示法

大O符号（Big O notation）：是用于描述函数渐进行为的数学符号。

推导大O阶方法：

1. 用常数1取代运行时间中的所有加法常数。
2. 在修改后的运行次数函数中，只保留最高阶项。
3. 如果最高阶项存在且不是1，则去除与这个项目相乘的常数。得到的结果就是大O阶。

使用大O的渐进表示法以后，上述Func1的时间复杂度为：O(N^2)

• N = 10 F(N) = 100
• N = 100 F(N) = 10000
• N = 1000 F(N) = 1000000

通过上面我们会发现大O的渐进表示法去掉了那些对结果影响不大的项，
简洁明了的表示出了执行次数。

有些算法的时间复杂度存在最好、平均和最坏情况：

• 最坏情况: 任意输入规模的最大运行次数(上界)
• 平均情况: 任意输入规模的期望运行次数
• 最好情况: 任意输入规模的最小运行次数(下界)

例如：在一个长度为N数组中搜索一个数据x

• 最好情况：1次找到
• 最坏情况：N次找到
• 平均情况：N / 2次找到

在实际中一般情况关注的是算法的最坏运行情况，所以数组中搜索数据时间复杂度为O(N)

2.3常见时间复杂度计算举例

实例1：

// 1.计算Func2的时间复杂度
void Func2(int N)
{int count = 0;for (int k = 0; k < 2 * N; ++k){++count;}int M = 10;while (M--){++count;}printf("%d\n", count);
}

基本操作执行了2N+10次

通过推导大O阶方法知道，时间复杂度为 O(N)

实例2：

//2.计算Func3的时间复杂度
void Func3(int N, int M)
{int count = 0;for (int k = 0; k < M; ++k){++count;}for (int k = 0; k < N; ++k){++count;}printf("%d\n", count);
}

基本操作执行了M+N次，有两个未知数M和N，

时间复杂度为 O(N)=O(M+N)

两个未知数位阶一样，所以都得留下

实例3：

//3.计算Func4的时间复杂度？
void Func4(int N)
{int count = 0;for (int k = 0; k < 100; ++k){++count;}printf("%d\n", count);
}

基本操作执行了100次，通过推导大O阶方法，时间复杂度为 O(1)

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

O(1)代表的是常数次

这样写其实是因为我们现在电脑的CPU运行的足够快，

这里我们可以写个代买来运行测试一下：

include<time.h>
int main()
{size_t begin = clock();//引头文件time.h//这个函数是用来记录时间的，到运行它的时候会记录一个时间，单位毫秒size_t n = 0;for (size_t i = 0;i < 1000000000;i++){n++;}size_t end = clock();printf("%d毫秒\n", end - begin);return 0;
}

实例4：

//4. 计算strchr的时间复杂度？
const char* strchr(const char* str, int character);

这里简单介绍一下strchr函数：

就是在字符串str里面找一个字符character，找不到：str++，找到就返回str地址，

大家也可以去cplusplus.com里面看 strchr（）函数的详细解释

如果整个字符串有n个元素，要找其中的一个元素，这个时候就有一下几种情况：

最好：O(1)，最坏：O(N)，平均：O(N/2)

这个时候我们一般取最坏的情况：O(N)

实例5：冒泡排序的时间复杂度

// 5.计算BubbleSort的时间复杂度？
void BubbleSort(int* a, int n)
{for (size_t end = n; end > 1; --end){int exchange = 0;for (size_t i = 1; i < end; ++i){if (a[i - 1] > a[i]){Swap(&a[i - 1], &a[i]);exchange = 1;}}if (exchange == 0)break;}
}

按最坏情况来看：

第一趟冒泡排序是：N-1，第二趟：N-2，第三趟N-3…最后一次是：1

可以看出来是需要进行：N*(N-1)/2 次循环

基本操作执行最好N次，最坏执行了 N * (N-1)/2 次，

通过推导大O阶方法+时间复杂度一般看最坏，时间复杂度为 O(N^2）

实例6：二分查找的时间复杂度

//6. 计算BinarySearch的时间复杂度？
int BinarySearch(int* a, int n, int x)
{assert(a);int begin = 0;int end = n - 1;// [begin, end]：begin和end是左闭右闭区间，因此有=号while (begin <= end){int mid = begin + ((end - begin) >> 1);if (a[mid] < x)begin = mid + 1;else if (a[mid] > x)end = mid - 1;elsereturn mid;}return -1;
}

二分法查找：每次查找，查找区间缩小一半，查找多少次，出2多少次

这里可以吧二分法查找想象成折纸，更容易理解一些
基本操作执行最好1次，最坏O(logN)次
（log以2为底的N，不好在计算机上表示，所以会简写为logN，其他底数不能省略）

时间复杂度为 O(logN)

实例7：

//7. 计算阶乘递归Fac的时间复杂度？
long long Fac(size_t N)
{if (0 == N)return 1;return Fac(N - 1) * N;
}

现基本操作递归了N次，时间复杂度为 O(N)

实例8：

//8. 计算斐波那契递归Fib的时间复杂度？
long long Fib(size_t N)
{if (N < 3)return 1;return Fib(N - 1) + Fib(N - 2);
}

基本操作递归了2^{N次，时间复杂度为O(2}N)。

像一个细胞分裂一样，n次分裂，就是2^N个

3.空间复杂度

空间复杂度也是一个数学表达式，是对一个算法在运行过程中临时（额外）占用存储空间大小的量度(如:函数中传入不算)

空间复杂度不是程序占用了多少bytes的空间，因为这个也没太大意义，所以空间复杂度算的是变量的个数。空间复杂度计算规则基本跟实践复杂度类似，也使用大O渐进表示法。

空间复杂度计算规则类似于时间复杂度，不是精确值，而实估计值

注意：函数运行时所需要的栈空间(存储参数、局部变量、一些寄存器信息等)在编译期间已经确定好了，因此空间复杂度主要通过函数在运行时候显式申请的额外空间来确定

实例1：冒泡排序的空间复杂度

// 计算BubbleSort的空间复杂度？
void BubbleSort(int* a, int n)
{assert(a);for (size_t end = n; end > 0; --end){int exchange = 0;for (size_t i = 1; i < end; ++i){if (a[i - 1] > a[i]){Swap(&a[i - 1], &a[i]);exchange = 1;}}if (exchange == 0)break;}
}

使用了常数个额外空间，所以空间复杂度为 O(1)

实例2：

// 计算Fibonacci的空间复杂度？
// 返回斐波那契数列的前n项
long long* Fibonacci(size_t n)
{if (n == 0)return NULL;long long* fibArray = (long long*)malloc((n + 1) * sizeof(long long));fibArray[0] = 0;fibArray[1] = 1;for (int i = 2; i <= n; ++i){fibArray[i] = fibArray[i - 1] + fibArray[i - 2];}return fibArray;
}

动态开辟了N个空间和若干个常数项，所以空间复杂度为 O(N)

实例3：

// 计算阶乘递归Fac的空间复杂度？
long long Fac(size_t N)
{if (N == 0)return 1;return Fac(N - 1) * N;
}

递归调用了N次，开辟了N个栈帧，每次开辟后没有被销毁，

每个栈帧使用了常数个空间。

空间复杂度为O(N）

这里如果使用循环就是O(1)

这里注意时因为空间是可以重复利用的，所以不会对一个数据重复开辟

4.复杂度的oj练习

4.1消失的数字：

消失的数字 - 力扣（LeetCode）

数组nums包含从0到n的所有整数，但其中缺了一个。
请编写代码找出那个缺失的整数(在 O(n) 时间内完成)注意：本题相对书上原题稍作改动示例 1：输入：[3,0,1]
输出：2示例 2：输入：[9,6,4,2,3,5,7,0,1]
输出：8

方法一：公式计算

将数组的大小+1进行累加 减去 将数组中的所有数加起来，即可求得

int main()
{int arr[] = { 9,6,4,2,3,5,7,0,1 };int sz = sizeof(arr) / sizeof(arr[0]);int add1 = 0;int add2 = 0;int i = 0;for (i = 0;i < sz;i++){add1 += arr[i];}for (i = 0;i < sz + 1;i++){add2 += i;}printf("%d\n", add2 - add1);return 0;
}

这里的时间复杂度为O(N)

空间复杂度为O(1)

方法二：异或

将n个数组元素于0~n+1的字符串异或，即可求得

int main()
{int arr[] = { 9,6,4,2,3,5,7,0,1 };int sz = sizeof(arr) / sizeof(arr[0]);int i = 0;int add = 0;for (i = 0;i < sz;i++){add ^= arr[0];}for (i = 0;i < sz+1;i++){add ^= i;}printf("%d\n", add);return 0;
}

这里的时间复杂度为O(N)

空间复杂度为O(1)

方法三:排序+二分查找

时间复杂度 O(N*logN)

4.2 旋转数组：

轮转数组 - 力扣（LeetCode）

给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。

示例 1:

输入: nums = [1,2,3,4,5,6,7], k = 3
输出: [5,6,7,1,2,3,4]
解释:
向右轮转 1 步: [7,1,2,3,4,5,6]
向右轮转 2 步: [6,7,1,2,3,4,5]
向右轮转 3 步: [5,6,7,1,2,3,4]

示例 2:

输入: nums = [-1,-100,3,99], k = 2
输出:[3,99,-1,-100]
解释:
向右轮转 1 步: [99,-1,-100,3]
向右轮转 2 步: [3,99,-1,-100]

提示：

1 <= nums.length <= 105
-231 <= nums[i] <= 231 - 1
0 <= k <= 105

进阶：

尽可能想出更多的解决方案，至少有 三种 不同的方法可以解决这个问题。
你可以使用空间复杂度为 O(1) 的 原地 算法解决这个问题吗？

方法一：一个一个的挪

void func1(int *a,int sz,int k)
{for (int i = 0;i < k;i++){int tmp = a[sz-1];for (int j = sz;j > 0;j--){a[j - 1] = a[j - 2];}a[0] = tmp;}
}
int main()
{int k = 0;scanf("%d", &k);int arr[9] = { 1,2,3,4,5,6,7,8,9 };int sz = sizeof(arr) / sizeof(arr[0]);k %= sz;//方法一：//func1(arr,sz,k);for (int i = 0; i < sz;i++){printf("%d ", arr[i]);}printf("\n");return 0;
}

但是这个方法在LeetCode上面编译不过去，因为时间复杂度有点大：O(N+K)

方法二：另一个数组进行存储

牺牲空间去换取时间效率，用另一个数组来进行存储，再复制回去

void func2(int* a, int sz, int k)
{int a2[10] = { 0 };int n = sz - k;int i = 0;int j = 0;for (i;i < n;i++){a2[i] = a[i];}for (j=0;j < k;j++,i++){a2[i] = a[i];}for (j = 0;j < sz;j++){a[j] = a2[j];}
}
int main()
{int k = 0;scanf("%d", &k);int arr[9] = { 1,2,3,4,5,6,7,8,9 };int sz = sizeof(arr) / sizeof(arr[0]);k %= sz;//方法二：func2(arr, sz, k);for (int i = 0; i < sz;i++){printf("%d ", arr[i]);}printf("\n");return 0;
}

方法三：颠倒数组

void reverse(int* a, int begin, int end)
{while (begin < end){int tmp = a[begin];a[begin] = a[end];a[end] = tmp;++begin;--end;}
}
void func3(int* a, int sz, int k)
{reverse(a, 0, sz - k - 1);reverse(a, sz-k, sz- 1);reverse(a, 0, sz - 1);
}
int main()
{int k = 0;scanf("%d", &k);int arr[9] = { 1,2,3,4,5,6,7,8,9 };int sz = sizeof(arr) / sizeof(arr[0]);k %= sz;//方法三：func3(arr, sz, k);for (int i = 0; i < sz;i++){printf("%d ", arr[i]);}printf("\n");return 0;
}