数据结构之时间复杂度与空间复杂度
算法的时间复杂度和空间复杂度是衡量算法效率的两个重要指标。
时间复杂度
时间复杂度描述了算法运行时间随输入规模增长的变化趋势。通常用大O符号（O）表示，忽略常数和低阶项，关注最高阶项。
常见时间复杂度
1. O(1)：常数时间复杂度，操作时间与输入规模无关。
2. O(log n)：对数时间复杂度，常见于二分查找。
3. O(n)：线性时间复杂度，操作时间与输入规模成正比。
4. O(n log n)：线性对数时间复杂度，常见于快速排序和归并排序。
5. O(n²)：平方时间复杂度，常见于简单排序算法如冒泡排序。
6. O(2^n)：指数时间复杂度，常见于某些递归算法。
7. O(n!)：阶乘时间复杂度，常见于排列组合问题。
时间复杂度的定义：在计算机科学中，
算法的时间复杂度是一个函数
，它定量描述了该算法的运行时间。一个算法执行所耗费的时间，从理论上说，是不能算出来的，只有你把你的程序放在机器上跑起来，才能知道。但是我们需要每个算法都上机测试吗？是可以都上机测试，但是这很麻烦，所以才有了时间复杂度这个
分析方式
。一个算法所花费的时间与其中语句的执行次数成正比例，算法中的
基本操作的执行次数，
为算法
的时间复杂度。
大O的渐进表示法
大O的渐进表示法（Big O Notation）是用于描述算法时间复杂度和空间复杂度的一种数学符号。它表示算法在最坏情况下，运行时间或所需空间随输入规模增长的上界。大O表示法关注的是增长趋势，忽略常数因子和低阶项，只保留最高阶项。
大O表示法的特点
-
忽略常数因子：例如，O(2n) 简化为 O(n)。
-
忽略低阶项：例如，O(n² + n) 简化为 O(n²)。
-
描述上界：大O表示法描述的是算法复杂度的上限，即最坏情况下的性能
例如：在一个长度为
N
数组中搜索一个数据
x
最好情况：
1
次找到。
最坏情况：
N
次找到。
平均情况：
N/2
次找到。
在实际中一般情况关注的是算法的
最坏运行情况
，所以数组中搜索数据时间复杂度为
O(N)。
分析以下实例的时间复杂度
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)。
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+M)。（如果M远大于N，则为O（M）反之，则为O(N)）
void Func4(int N)
{
int count = 0;
for (int k = 0; k < 100; ++ k)
{
++count;
}
printf("%d\n", count);
}
基本操作执行了
100
次，通过推导大
O
阶方法，时间复杂度为
O(1)。（O(1）不是代表一次，而是代表常数次 ）
// 计算strchr的时间复杂度？strchr用于字符串中查找特定字符的位置
const char * strchr ( const char * str, int character );
基本操作执行最好
1
次，最坏
N
次，时间复杂度一般看最坏，时间复杂度为
O(N)。
//计算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;
}
}
基本操作执行最好
N
次，最坏执行了
(N*(N+1)/2
次，通过推导大
O
阶方法
+
时间复杂度一般看最
坏，时间复杂度为
O(N^2)。（关于具体的推导过程可自行查找）
// 二分查找函数
int binarySearch(int arr[], int left, int right, int target) {
while (left <= right) {
int mid = left + (right - left) / 2;
// 检查目标值是否在中间
if (arr[mid] == target)
return mid;
// 如果目标值更大，忽略左半部分
if (arr[mid] < target)
left = mid + 1;
// 如果目标值更小，忽略右半部分
else
right = mid - 1;
}
// 如果未找到目标值，返回 -1
return -1;
}
基本操作执行最好
1
次，最坏
O(logN)
次，时间复杂度为
O(logN) ps
：
logN
在算法分析中表示是底
数为
2
，对数为
N
。有些地方会写成
lgN
。
// 计算阶乘递归Fac的时间复杂度？
long long Fac(size_t N)
{
if(0 == N)
return 1;
return Fac(N-1)*N;
}
通过计算分析发现基本操作递归了
N
次，时间复杂度为
O(N)。
// 计算斐波那契递归Fib的时间复杂度？
long long Fib(size_t N)
{
if(N < 3)
return 1;
return Fib(N-1) + Fib(N-2);
}
通过计算分析发现基本操作递归了
2^N
次，时间复杂度为
O(2^N)
。
空间复杂度
空间复杂度也是一个数学表达式，是对一个算法在运行过程中
临时占用存储空间大小的量度
。
空间复杂度不是程序占用了多少
bytes
的空间，因为这个也没太大意义，所以空间复杂度算的是变量的个数。
空间复杂度计算规则基本跟实践复杂度类似，也使用
大O渐进表示法
。
注意：
函数运行时所需要的栈空间
(
存储参数、局部变量、一些寄存器信息等
)
在编译期间已经确定好了，因
此空间复杂度主要通过函数在运行时候显式
申请的额外空间
来确定。
常见空间复杂度
1. O(1)：常数空间复杂度，算法所需空间固定，与输入规模无关。
2. O(n)：线性空间复杂度，算法所需空间与输入规模成正比。
3. O(n²)：平方空间复杂度，常见于某些二维数组操作。
分析下列实例的空间复杂度
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)。
// 计算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)。
// 计算阶乘递归Fac的空间复杂度？
long long Fac(size_t N)
{
if(N == 0)
return 1;
return Fac(N-1)*N;
}
递归调用了
N
次，开辟了
N
个栈帧，每个栈帧使用了常数个空间。空间复杂度为
O(N)。
long long Fib(size_t N)
{
if (N < 3)
return 1;
return Fib(N - 1) + Fib(N - 2);
}函数的空间复杂度为 O(N)，主要由递归调用栈的深度决定。
例题
面试题 17.04. 消失的数字 - 力扣（LeetCode）
思路1：排序 再依次查找 如果下一个值不等于前一个值加一 则为消失的数字
时间复杂度分析：排序算法如qsort O(N*logN) + 遍历O(N) 时间复杂度太大 不合适
思路2：求和0到N 再依次减去数组中值 剩下的值则为消失的数字 时间复杂度O(N) 但是数字太大时候有溢出的风险
int missingNumber(vector<int>& nums)
{
int n =nums.size();
int ret = (0+n)*(n+1)/2;
for(int i = 0; i < n ; i++)
{
ret -=nums[i];
}
return ret;
}思路3：异或 相同的值异或后为0
//相同的值异或后结果为0
int missingNumber(int* nums, int numsSize)
{
int N = numsSize;
int x = 0;
for (int i = 0; i < N; i++)
{
x ^= nums[i];
}
//异或0-n的数字
for (int j = 0; j<= N; j++)
{
x ^= j;
}
return x;
}
总结
- 时间复杂度：衡量算法运行时间。
- 空间复杂度：衡量算法内存使用。
两者共同决定了算法的效率，是算法设计和分析的关键。