算法效率的计算
目录
- 一、如何衡量一个算法的好坏？
- 二、时间复杂度
- 1. 时间复杂度的计算方法
- 2. 时间复杂度习题
- 三、空间复杂度
- 1. 空间复杂度的计算方法
- 2. 空间复杂度习题
- 四、常见复杂度对比
- 五、复杂度oj题
- 1. 消失的数字
- 2. 轮转数组
一、如何衡量一个算法的好坏？
如果一个算法运行速度快且消耗内存少，那么该算法一定是一个效率高的好算法。那么如何计算一个算法的速度和消耗的内存呢？通常我们使用时间复杂度和空间复杂度来衡量一个算法的好坏，并且使用大O表示法来表示。
二、时间复杂度
1. 时间复杂度的计算方法
一、确定基本操作
首先，明确算法中的基本操作。基本操作通常是指算法中执行次数最多或者对时间影响最大的操作。例如，在一个循环中，循环体的执行次数通常是基本操作；在排序算法中，比较操作和交换操作可能是基本操作。
二、分析基本操作的执行次数与问题规模的关系
- 用问题规模的变量来表示基本操作的执行次数。例如，如果算法是对一个长度为 n 的数组进行操作，那么问题规模通常用 n 表示。
- 分析算法的结构，确定基本操作的执行次数与问题规模之间的关系。这可能需要对算法进行逐步分析，考虑不同的情况和分支。
三、用大 O 记号表示时间复杂度
- 忽略低阶项和系数。在表示时间复杂度时，只关注最高阶项，因为当问题规模足够大时，低阶项和系数对时间的影响相对较小。
- 根据基本操作的执行次数与问题规模的关系，常见的时间复杂度级别有常数阶 O (1)、对数阶 O (log n)、线性阶 O (n)、线性对数阶 O (n log n)、平方阶 O (n²) 等。
用作者的话来说，就是有循环就计算整个算法中循环语句的执行次数，没有循环就计算整个算法所执行的所有语句数。然后用问题的规模的变量把这个计算结果表示出来，最后使用大O表示法去掉最高项的系数，只保留最高项的阶数，结果就是该算法的时间复杂的大O表示法。如果该算法中有函数调用或者递归也是同样的计算方法。
2. 时间复杂度习题
例题1
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;
}
｝
首先，有循环就计算循环语句的执行次数，n2 + 2n + 10
其次，从该函数的参数判断该算法的规模为 n
接着，使用规模变量表示前面的执行次数，n2 + 2n + 10
最后，使用大O表示法，去掉最高阶系数，只保留最高阶，O(n2)
例题2
下面是一个计算前 n 项正整数之和的算法：
// 计算前 n 项和
long long sum_first_n(int n)
{
int i;
long long sum = 0;
for (i = 1; i <= n; ++i)
sum += i;
// 返回
return sum;
}
首先，有循环，那么就计算循环语句的执行次数，n。
然后，该算法是计算前 n 项正整数的和，规模变量为 n。
接着用规模变量表示前面计算的执行次数，n。
最后使用大O表示法，去掉最高阶系数，只保留最高阶，O(n)。
例题3
// 计算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
如果题目说明 M 远大于 N，则 O(M)，如果 N 远大于 M，则O(N)，如果没有说明则 O(M+N)。
例题4
// 计算Func4的时间复杂度？
void Func4(int N)
{
int count = 0;
for (int k = 0; k < 100; ++ k)
{
++count;
}
printf("%d\n", count);
}
循环语句执行次数：100
问题规模变量表示：100
结果为常数，那就是常数阶O(1)，不管这个常数多大，只要是一个常数那都是O(1)
例题5
// 计算strchr的时间复杂度？
const char * strchr ( const char * str, int character );
库函数 strchr() 的功能是在一个字符串中查找指定字符，如果找到了就返回该字符的地址，如果没找到就返回空指针。
那么通过计算，该算法的时间复杂度并不唯一，如果带查找的字符刚好在第一个，那么只需要查找一次，时间复杂度也就是O(1)；如果带查找的字符刚好在最后一个，那么需要查找 n 次，时间复杂度也就是O(n)。
在这种存在最好和最坏的情况的算法中，通常是取最坏的情况。那么该算法的时间复杂度就是 O(n)。
例题6
下面是一个优化过后的冒泡排序：
// 计算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;
}
}
该冒泡排序算法也存在最好和最坏两种情况：
（1）当待排序数组完全有序，那么第一轮比较之后就会跳出循环。那么循环中 if 条件语句执行的次数为 n-1，其时间复杂度也就是 O(n)
（2）当待排序数组完全逆序，那么冒泡排序就会一直执行到结束。那么循环中 if 条件语句的执行次数为 (n-1)+(n-2)+…+1，其时间复杂度为 O(n2)
例题7
下面是一个二分查找的算法：
// 计算BinarySearch的时间复杂度？
int BinarySearch(int* a, int n, int x)
{
assert(a);
int begin = 0;
int end = n-1;
while (begin < end)
{
// 取得中间数
int mid = begin + ((end-begin)>>1);
// 判断
if (a[mid] < x)
begin = mid+1;
else if (a[mid] > x)
end = mid;
else
return mid;
}
return -1;
}
二分查找是在 n 个有序的数中查找一个数，而且每次查找都可以去掉一半的数，也就是剩下 n/2 个数。最坏的情况就是查找到最后一个数，也就是 n/2/2/2…/2 = 1，即 2k = n，k = log2n，这个 k 也就是要查找的次数，且每次查找所执行的语句也是常数，所以该算法的时间复杂度就是 O(log2n)，也就是上面说的对数阶。
例题8
下面是计算正整数 n 的阶乘的递归算法：
// 计算阶乘递归Fac的时间复杂度？
long long Fac(size_t N)
{
if(0 == N)
return 1;
return Fac(N-1)*N;
}
通过计算，该函数加上递归一共需要被调用 N+1 次，每次调用该函数执行常数条语句，所以该算法的时间复杂度为 O(n)
例题9
下面是第 n 项斐波那契数列的递归算法：
// 计算斐波那契递归Fib的时间复杂度？
long long Fib(size_t N)
{
if(N < 3)
return 1;
return Fib(N-1) + Fib(N-2);
}
首先，递归调用一次执行常数条语句，那么一共递归调用多少次？
如上图所示，我们把缺失的项设置为 k，那么递归调用的次数为：20 + 21 + 22 +…+ 2n-1 - k = 2n - 1 - k，相比于 2n 来说 1+k 显得微不足道，所以该求斐波那契第 n 项的递归算法的时间复杂度为 O(2n)
三、空间复杂度
1. 空间复杂度的计算方法
有了前面时间复杂度的计算方法，那么空间复杂度的计算就要简单很多了。
（1）统计创建变量的个数（不管是什么类型）
（2）用问题的规模变量表示变量的总个数
（3）大O表示法，去掉最高阶的系数，只保留最高阶
2. 空间复杂度习题
习题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;
}
}
由于在执行算法的过程中只开辟了常数个变量（end、i 和 exchange），所以该算法的空间复杂度为 O(1)
习题2
下面是阶乘的递归算法：
// 计算阶乘递归Fac的空间复杂度？
long long Fac(size_t N)
{
if(N == 0)
return 1;
return Fac(N-1)*N;
}
虽然在递归的过程中没有开辟新的变量，但是每次递归都需要开辟栈帧空间，一共递归 n+1 次，开辟了 n+1 个栈帧空间，所以该算法的空间复杂度为 O(n)
习题3
下面是第 n 项斐波那契数列的递归算法：
// 计算斐波那契递归Fib的时间复杂度？
long long Fib(size_t N)
{
if(N < 3)
return 1;
return Fib(N-1) + Fib(N-2);
}
前面通过画图的方式的出，该递归需要调用 2n 层级的次数，那么是否需要开辟 2n 层级的函数栈桢？
答案肯定不是，仔细阅读代码，你会发现，每次递归调用函数 Fib 时，它都会先调用左边的 Fib(N-1)，然后再在里面调用他自己的 Fib(N-1)，直到最后一次递归时它的 N-1 < 3 时才会返回上一层递归，然后调用该层递归的 Fib(N-2)。如下图：
所以，该算法运行时函数栈帧消耗的最大层数为 n，所以该算法的空间复杂度为 O(n)
四、常见复杂度对比
上述图片均来自比特的课件哈，作者比较懒也不会画。
五、复杂度oj题
1. 消失的数字
题目描述： 数组nums包含从 0 到 n 的所有整数，但其中缺了一个。请编写代码找出那个缺失的整数。你有办法在 O(n) 的时间复杂度内完成吗？
注意：本题相对书上原题稍作改动
示例 1：
输入：[3,0,1]
输出：2
示例 2：
输入：[9,6,4,2,3,5,7,0,1]
输出：8
题目OJ链接： 链接: link
题目解析：
（1）题目要求时间复杂度需要 <= O(n)
（2）三种算法：
a. 计算 0 - n 的和然后减去数组的每个元素，结果就是缺失的数
// 计算 0 - n 的和，然后减去数组的每个元素
int find_missing_num(int *arr, int sz)
{
// 计算 0-n 之和
int sum = (sz + 1) * sz / 2;
// 减去数组的每个元素
int i;
for (i = 0; i < sz; ++i)
{
sum -= arr[i];
}
// 返回
return sum;
}
时间复杂度： O(n)
空间复杂度： O(1)
b. 用 0 - n 与数组的每个元素异或，结果就是缺失的数
int find_missing_num(int* arr, int sz)
{
int result = sz;
int i;
for (i = 0; i < sz; ++i)
{
result ^= i ^ arr[i];
}
// 返回
return result;
}
由于循环是 0 - n-1，所以 result 的初值为 sz。
时间复杂度： O(n)
空间复杂度： O(1)
c. 使用 calloc() 函数动态开辟一个大小为 n+1 的 int 数组，该数组用来统计 0 - n 的出现次数，遍历原数组，记录出现次数，然后遍历次数数组，出现次数为 0 的就是缺失的数。
int find_missing_num(int* arr, int sz)
{
// 动态开辟次数数组
int* times = (int*)calloc((sz + 1), sizeof(int));
// 遍历原数组统计次数
int i;
for (i = 0; i < sz; ++i)
++times[arr[i]];
// 遍历次数数组找缺失数
for (i = 0; i <= sz; ++i)
{
if (0 == times[i])
break;
}
// 释放
free(times);
times = NULL;
// 返回
return i;
}
时间复杂度： O(n)
空间复杂度： O(n)
2. 轮转数组
题目描述： 给定一个整数数组 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
题目OJ链接： 链接: link
题目解析：
（1）像这种旋转数组或者字符串的问题，不管是右旋转还是坐旋转，当旋转次数为其长度的整数倍时，就会复原。也就是旋转的周期是其长度，如：1,2,3,4，右旋转或者左旋转 4n 次后复原。所以，实际的旋转次数需要对其长度取余。
（2）三种解法：
a. 暴力求解法
就是直接一步一步旋转，没有任何技巧可言
// 暴力求解法
void rotate_arr_i(int* arr, int sz, int k)
{
// 实际旋转次数
int n = k % sz;
// 旋转
while (n--)
{
// 存储尾元素
int tmp = arr[sz - 1];
// 前面元素往后移
int i;
for (i = sz - 1; i > 0; ++i)
arr[i] = arr[i - 1];
// 尾元素放开头
arr[0] = tmp;
}
}
时间复杂度： O(n2)
空间复杂度： O(1)
b. 三步逆序法（三种里面最优）
先计算实际旋转次数 k，然后把后 k 项逆序，再把前 sz-k 项逆序，最后整个数组逆序，就是想要的结果。
// 三步逆序法
// 逆序
void reverse(int* left, int* right)
{
while (left < right)
{
// 交换
int tmp = *left;
*left = *right;
*right = tmp;
// 下一组
++left;
--right;
}
}
// 三步
void rotate_arr_i(int* arr, int sz, int k)
{
// 实际旋转次数
k %= sz;
// 三步逆序
reverse(arr + sz - k, arr + sz - 1);
reverse(arr, arr + sz - k - 1);
reverse(arr, arr + sz - 1);
}
时间复杂度： O(n)
空间复杂度： O(1)
c. 额外开辟数组法
这是一个空间换时间的方法，额外开辟一个大小相同的动态数组，然后算出实际旋转次数 k，把后 k 项放在新数组前面，再把前 sz-k 项放在新数组后面，最后把新数组拷贝到原数组。
// 额外开辟数组法
void rotate_arr_i(int* arr, int sz, int k)
{
// 实际旋转次数
k %= sz;
// 开辟额外数组
int* tmp = (int*)malloc(sizeof(int) * sz);
// 把原数组旋转后的顺序拷贝到新数组
int i;
for (i = 0; i < k; ++i)
tmp[i] = arr[sz - k + i];
for (i = 0; i < sz - k; ++i)
tmp[k - 1 + i] = arr[i];
// 把新数组拷贝到原数组
for (i = 0; i < sz; ++i)
arr[i] = tmp[i];
// 释放额外数组
free(tmp);
}
时间复杂度： O(n)
空间复杂度： O(n)