企业官网建设流程全解析

一.概念

1.1时间复杂度的定义

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

我们大概看

1.2大O的渐进表示法

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

推导大O阶方法：

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

2、在修改后的运行次数函数中，只保留最高阶项。

3、如果最高阶项存在且不是1，则去除与这个项目相乘的常数。得到的结果就是大O阶。

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

最坏情况：任意输入规模的最大运行次数(上界)

平均情况：任意输入规模的期望运行次数

最好情况：任意输入规模的最小运行次数(下界)

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

最好情况：1次找到

最坏情况：N次找到

平均情况：N/2次找到

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

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

实例1：

// 1. O(M+N) 形式 void func1(int M, int N) { for (int i = 0; i < M; i++); // 执行 M 次 for (int i = 0; i < N; i++); // 执行 N 次 // 总共 M+N 次。如果 M 远大于 N，则近似为 O(M) } // 2. O(max(M, N)) 形式 void func2(int M, int N) { int i = 0, j = 0; while (i < M || j < N) { // 取决于较长的一方 if (i < M) i++; if (j < N) j++; } } int main() { // 测试 M 远大于 N 的情况 int M = 10000; int N = 5; printf("开始调用 func1(M, N)...\n"); func1(M, N); // 这个函数内部会循环 10000 + 5 = 10005 次。 // 因为 M 远大于 N，所以整体耗时几乎等同于 O(M)。 printf("开始调用 func2(M, N)...\n"); func2(M, N); // 这个函数内部会循环 max(10000, 5) = 10000 次。 printf("调用结束。\n"); return 0; }

实例2：

// 时间复杂度：O(1) 不代表执行 1 次，代表执行常数次 void func(int N) { int K = 100; // K 是一个固定常数 // 实际执行次数取决于 N 和 K 谁更小 int limit = (N < K) ? N : K; // 无论 N 是一万还是一百万，这个循环最多只执行 K（100）次 // 100 是常数，不随 N 增长而增长，所以是 O(1) for (int i = 0; i < limit; i++); } int main() { // 测试 1：N 小于常数 K func(5); // 实际执行 5 次，仍是常数次，O(1) // 测试 2：N 远大于常数 K func(1000000); // 实际执行 100 次，仍是常数次，O(1) return 0; }

实例3：

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

实例4：

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

画了一棵递归树，展示了函数调用的展开过程：

1. 第一层（根节点）：Fib(N)，调用次数为1次，即 2^0。

2. 第二层：Fib(N-1)和Fib(N-2)，调用次数为2次，即 2^1。

3. 第三层：Fib(N-2)、Fib(N-3)、Fib(N-3)、Fib(N-4)，调用次数为4次，即 2^2。

4. ...（以此类推）：每一层的调用次数都在翻倍。

5. 最后一层（叶子节点）：当递归到Fib(3)时，会分支出Fib(2)和Fib(1)。由于 N<3N<3 时直接返回 1，递归终止。

清晰标注了每层的节点数：

• 第 1 层：2^0

• 第 2 层：2^1

• 第 3 层：2^2

• ...

• 第 N−2 层：2^N−2

有二种办法：

第一种：等比数列

1. 累加递归调用次数（列出等比数列）
将每一层的节点数相加：

总次数=2^0+2^1+2^2+...+2^N−2

2. 识别数列
这是一个首项 a1=2^0，公比 q=2，项数为N−1 的等比数列

第二种：错位相减法

1.4.常见复杂度对比

二.题目

面试题 17.04. 消失的数字 - 力扣（LeetCode）

思路1：求和0到N，再依次减去数组中值，剩下的那个就是消失数字 代码： int missingNumber(int* nums, int numsSize) { int N = numsSize; int ret = (0+N)*(N+1)/2; for(int i = 0; i < numsSize; ++i) { ret -= nums[i]; } return ret; }

思路2：异或

相同为零，相异为一

int missingNumber(int* nums, int numsSize) { int N = numsSize; int x = 0; for (int i = 0; i < numsSize; ++i) { x ^= nums[i]; } for (int j = 0; j <= N; ++ j) { x ^= j; } return x; }

189. 轮转数组 - 力扣（LeetCode）

解题：

初始状态

索引: 0 1 2 3 4 5 6

数值: [1, 2, 3, 4, 5, 6, 7]

└───┬────┘ └──┬──┘

前 n-k 个 后 k 个

(长度4) (长度3)

第一步：翻转前 n-k 个 (前4个)

操作: 反转 [1, 2, 3, 4] -> [4, 3, 2, 1]

状态: [4, 3, 2, 1, 5, 6, 7]

↑ ↑

左指针 右指针

第二步：翻转后 k 个 (后3个)

操作: 反转 [5, 6, 7] -> [7, 6, 5]

状态: [4, 3, 2, 1, 7, 6, 5]

↑ ↑

左指针 右指针

第三步：整体翻转 (全部7个)

操作: 反转整个数组 -> [5, 6, 7, 1, 2, 3, 4]

状态: [5, 6, 7, 1, 2, 3, 4]

↑ ↑

左指针 右指针

oid reverse(int* a, int left, int right) { while (left < right) { int tmp = a[left]; a[left] = a[right]; a[right] = tmp; ++left; --right; } } void rotate(int* nums, int numsSize, int k) { if (numsSize == 0) return; k %= numsSize; // 修正：赋值 if (k == 0) return; // 可选：提前返回 reverse(nums, 0, numsSize - k - 1); reverse(nums, numsSize - k, numsSize - 1); reverse(nums, 0, numsSize - 1);

二.空间复杂度

空间复杂度也是一个数学表达式，是对一个算法在运行过程中临时占用存储空间大小的量度。

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

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

实例：

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)

即冒泡排序的空间复杂度为 O(1)，属于原地排序算法（in-place sort）。