企业官网建设流程全解析

// 尾递递归 ： 求和操作是在“递”操作上执行的
// 普通递归：求和操作是在“归”这一步执行的

//普通的递归

int recur(int n)
{
if (n == 1)
{
return 1;

}
int res = recur(n - 1);
return n + res;
}

//尾递归
int tailRecur(int n, int res)
{
if (n == 0)
{
return res;
}
return tailRecur(n - 1, res + n);
}

//递归树 分区治理

//一斐波那契数为例

int fab(int n)
{
if (n == 1 || n == 2)
{
return n - 1;
}
int res = fab(n - 1) + fab(n - 2);
return res;
}

//递归的这种模式与 先进后出 原则上 有 异曲同工之妙

//使用 显示的栈 来模拟 调用栈的行为

int forLoopRecur(int n)
{
//使用一个显示的栈来模拟系统调用栈
stack<int> stack;
int res = 0;
//递：递归调用
for (int i = n;i > 0;i--)
{
// // 通过“入栈操作”模拟“递”
stack.push(i);
}
// 归：返回结果
while (!stack.empty())
{// 通过“入栈操作”模拟“递”
res += stack.top();
stack.pop();

}
// res = 1 + 2 + 3... + n;
return res;
}

时间复杂度¶

运行时间可以直观且准确地反映算法的效率。如果我们想准确预估一段代码的运行时间，应该如何操作呢？

1. 确定运行平台，包括硬件配置、编程语言、系统环境等，这些因素都会影响代码的运行效率。
2. 评估各种计算操作所需的运行时间，例如加法操作+需要 1 ns ，乘法操作*需要 10 ns ，打印操作print()需要 5 ns 等。
3. 统计代码中所有的计算操作，并将所有操作的执行时间求和，从而得到运行时间。

但实际上，统计算法的运行时间既不合理也不现实。

时间复杂度分析统计的不是算法运行时间，而是算法运行时间随着数据量变大时的增长趋势。

// 算法 A 的时间复杂度：常数阶 void algorithm_A(int n) { cout << 0 << endl; } // 算法 B 的时间复杂度：线性阶 void algorithm_B(int n) { for (int i = 0; i < n; i++) { cout << 0 << endl; } } // 算法 C 的时间复杂度：常数阶 void algorithm_C(int n) { for (int i = 0; i < 1000000; i++) { cout << 0 << endl; } }

图 2-7 展示了以上三个算法函数的时间复杂度。

• 算法A只有 个打印操作，算法运行时间不随着 增大而增长。我们称此算法的时间复杂度为“常数阶”。
• 算法B中的打印操作需要循环 次，算法运行时间随着 增大呈线性增长。此算法的时间复杂度被称为“线性阶”。
• 算法C中的打印操作需要循环 次，虽然运行时间很长，但它与输入数据大小 无关。因此C的时间复杂度和A相同，仍为“常数阶”

以冒泡排序为例，外层循环执行 n-1 次，内层循环执行 n/ 2 次，因此时间复杂度为 ：（n - 1）/ 2

“最差时间复杂度”对应函数渐近上界，使用大 记号表示。相应地，“最佳时间复杂度”对应函数渐近下界

我们在实际中很少使用最佳时间复杂度，因为通常只有在很小概率下才能达到，可能会带来一定的误导性。而最差时间复杂度更为实用，因为它给出了一个效率安全值，让我们可以放心地使用算法。

我们通常使用最差时间复杂度作为算法效率的评判标准。

空间复杂度¶

空间复杂度（space complexity）用于衡量算法占用内存空间随着数据量变大时的增长趋势。这个概念与时间复杂度非常类似，只需将“运行时间”替换为“占用内存空间”。

一般情况下，空间复杂度的统计范围是“暂存空间”加上“输出空间”。

暂存空间可以进一步划分为三个部分。

• 暂存数据：用于保存算法运行过程中的各种常量、变量、对象等。
• 栈帧空间：用于保存调用函数的上下文数据。系统在每次调用函数时都会在栈顶部创建一个栈帧，函数返回后，栈帧空间会被释放。
• 指令空间：用于保存编译后的程序指令，在实际统计中通常忽略不计。

我们通常只关注最差空间复杂度。这是因为内存空间是一项硬性要求，我们必须确保在所有输入数据下都有足够的内存空间预留。

1. 常数阶 ¶

常数阶常见于数量与输入数据大小 无关的常量、变量、对象。

2. 线性阶 ¶

线性阶常见于元素数量与 成正比的数组、链表、栈、队列等：

3. 平方阶 ¶

平方阶常见于矩阵和图，元素数量与 成平方关系

4. 指数阶 ¶

指数阶常见于二叉树。

5. 对数阶 ¶

对数阶常见于分治算法。例如归并排序，输入长度为 的数组，每轮递归将数组从中点处划分为两半