当前位置：首页 > news >正文

时间复杂度和空间复杂度

news 来源：原创 2025/8/25 23:53:26

🌟 各位看官好，我是maomi_9526！

🌍 种一棵树最好是十年前，其次是现在！

🚀 今天来学习C语言的相关知识。

👍 如果觉得这篇文章有帮助，欢迎您一键三连，分享给更多人哦

1. 算法效率

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

1.2 算法的复杂度

1.3 复杂度在校招中的考察

2. 时间复杂度

2.1 时间复杂度的概念

2.2 大O的渐进表示法

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

3. 空间复杂度

3.1 空间复杂度计算

3.2 动态分配内存的空间复杂度

4. 常见复杂度对比

1. 算法效率

在编写算法时，如何衡量其优劣成为一个重要的课题。直观地看，算法的效率可以从运行时间和内存占用两个维度来衡量。对于同一问题的不同算法，我们通常希望选择一个运行时间短、内存占用小的算法。但实际上，常常会面临时间和空间的平衡问题，特别是在处理大规模数据时，时间复杂度和空间复杂度会影响算法的实际运行表现。

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

我们通过对斐波那契数列的计算来举例，斐波那契数列的递归实现方式非常简洁，但简洁并不总是代表高效。为了更好地理解算法的好坏，我们需要考量它的时间复杂度和空间复杂度。

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

上述递归算法虽然简单，但其时间复杂度是指数级别的（O(2^N)），这是因为它会进行大量重复的计算。通过分析这种算法的复杂度，我们能更好地判断其在实际问题中的适用性。

1.2 算法的复杂度

一个算法在执行时消耗的资源主要是时间和空间。在早期，计算机的存储容量较小，因此空间复杂度常常成为优化的重点。随着计算机硬件的发展，现在我们更多关注的是时间复杂度，即算法运行的速度。

时间复杂度衡量的是算法运行的速度，空间复杂度则衡量的是算法运行所需的内存空间。在计算机科学中，时间复杂度和空间复杂度是评估算法好坏的重要标准。

1.3 复杂度在校招中的考察

在编程面试中，时间复杂度和空间复杂度的分析是考察一个候选人算法能力的重要环节。例如，考虑如下斐波那契数列的递归实现：

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

此算法通过递归计算斐波那契数列的值，但它的时间复杂度是指数级别的。分析这种算法的复杂度对于求解实际问题时是非常重要的。

2. 时间复杂度

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

Func1中的基本操作执行次数为 N² + 2N + 10 次。为了简化，我们忽略常数项和低阶项，最终得出时间复杂度为 O(N²)。

2.2 大O的渐进表示法

大O符号（Big O notation）用来描述函数在输入规模增大时的渐进行为。通过大O符号，我们可以简化算法的时间复杂度表示，忽略不重要的部分。例如，Func1 的时间复杂度为 O(N²)，因为 N²项在算法中占主导地位。

大O表示法的推导步骤包括：

替换掉所有加法常数；
保留最高阶项；
去除与最高阶项相乘的常数。

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

对于不同的算法，可以根据其执行次数推导出时间复杂度：

Func2 时间复杂度：O(N)
Func3 时间复杂度：O(N + M)
Func4 时间复杂度：O(1)

3. 空间复杂度

空间复杂度描述了一个算法在执行过程中所需的额外空间。不同于程序占用的总内存，空间复杂度主要衡量的是在算法运行时显式分配的额外内存空间。与时间复杂度类似，空间复杂度也使用大O表示法来描述。

3.1 空间复杂度计算

例如，对于以下递归函数：

long long Fac(size_t N)
{if (N == 0)return 1;return Fac(N - 1) * N;
}

该函数的空间复杂度是 O(N)，因为递归调用的深度为 N，每次调用都需要一个新的栈帧。

3.2 动态分配内存的空间复杂度

如果一个函数动态分配了内存，例如：

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

此函数的空间复杂度为 O(N)，因为它为 n+1 个元素分配了内存。

4. 常见复杂度对比

常见的时间复杂度和空间复杂度包括：

复杂度	含义
O(1)	常数时间或空间；
O(log N)	对数时间复杂度，例如二分查找；
O(N)	线性时间复杂度，例如遍历数组；
O(N²)	二次方时间复杂度，例如冒泡排序；
O(2^N)	指数级时间复杂度，例如递归的斐波那契数列。

1. 算法效率

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

1.2 算法的复杂度

1.3 复杂度在校招中的考察

2. 时间复杂度

2.1 时间复杂度的概念

2.2 大O的渐进表示法

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

3. 空间复杂度

3.1 空间复杂度计算

3.2 动态分配内存的空间复杂度

4. 常见复杂度对比

相关文章：