一.概念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(MN) 形式 void func1(int M, int N) { for (int i 0; i M; i); // 执行 M 次 for (int i 0; i N; i); // 执行 N 次 // 总共 MN 次。如果 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 是一万还是一百万这个循环最多只执行 K100次 // 100 是常数不随 N 增长而增长所以是 O(1) for (int i 0; i limit; i); } int main() { // 测试 1N 小于常数 K func(5); // 实际执行 5 次仍是常数次O(1) // 测试 2N 远大于常数 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通过计算分析发现基本操作递归了N次时间复杂度为O(N)。递归时间复杂度所有递归调次数累加实例4// 计算斐波那契递归Fib的时间复杂度 long long Fib(size_t N) { if(N 3) return 1; return Fib(N-1) Fib(N-2); }画了一棵递归树展示了函数调用的展开过程第一层根节点Fib(N)调用次数为1次即 2^0。第二层Fib(N-1)和Fib(N-2)调用次数为2次即 2^1。第三层Fib(N-2)、Fib(N-3)、Fib(N-3)、Fib(N-4)调用次数为4次即 2^2。...以此类推每一层的调用次数都在翻倍。最后一层叶子节点当递归到Fib(3)时会分支出Fib(2)和Fib(1)。由于 N3N3 时直接返回 1递归终止。清晰标注了每层的节点数第 1 层2^0第 2 层2^1第 3 层2^2...第 N−2 层2^N−2有二种办法第一种等比数列1. 累加递归调用次数列出等比数列将每一层的节点数相加总次数2^02^12^2...2^N−22. 识别数列这是一个首项 a12^0公比 q2项数为N−1 的等比数列第二种错位相减法1.4.常见复杂度对比二.题目面试题 17.04. 消失的数字 - 力扣LeetCode思路1求和0到N再依次减去数组中值剩下的那个就是消失数字 代码 int missingNumber(int* nums, int numsSize) { int N numsSize; int ret (0N)*(N1)/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。
数据结构：时间复杂度
一.概念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(MN) 形式 void func1(int M, int N) { for (int i 0; i M; i); // 执行 M 次 for (int i 0; i N; i); // 执行 N 次 // 总共 MN 次。如果 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 是一万还是一百万这个循环最多只执行 K100次 // 100 是常数不随 N 增长而增长所以是 O(1) for (int i 0; i limit; i); } int main() { // 测试 1N 小于常数 K func(5); // 实际执行 5 次仍是常数次O(1) // 测试 2N 远大于常数 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通过计算分析发现基本操作递归了N次时间复杂度为O(N)。递归时间复杂度所有递归调次数累加实例4// 计算斐波那契递归Fib的时间复杂度 long long Fib(size_t N) { if(N 3) return 1; return Fib(N-1) Fib(N-2); }画了一棵递归树展示了函数调用的展开过程第一层根节点Fib(N)调用次数为1次即 2^0。第二层Fib(N-1)和Fib(N-2)调用次数为2次即 2^1。第三层Fib(N-2)、Fib(N-3)、Fib(N-3)、Fib(N-4)调用次数为4次即 2^2。...以此类推每一层的调用次数都在翻倍。最后一层叶子节点当递归到Fib(3)时会分支出Fib(2)和Fib(1)。由于 N3N3 时直接返回 1递归终止。清晰标注了每层的节点数第 1 层2^0第 2 层2^1第 3 层2^2...第 N−2 层2^N−2有二种办法第一种等比数列1. 累加递归调用次数列出等比数列将每一层的节点数相加总次数2^02^12^2...2^N−22. 识别数列这是一个首项 a12^0公比 q2项数为N−1 的等比数列第二种错位相减法1.4.常见复杂度对比二.题目面试题 17.04. 消失的数字 - 力扣LeetCode思路1求和0到N再依次减去数组中值剩下的那个就是消失数字 代码 int missingNumber(int* nums, int numsSize) { int N numsSize; int ret (0N)*(N1)/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。
