网站关键词快速优化,wordpress网站被黑了,360免费wifi手机版,小红书的网络营销模式这周主要总结了时间复杂度的学习#xff0c;跟小伙伴们分享下#xff0c;欢迎指正。一、为何需要分析算法复杂度挺多同学本科都学习过数据结构和算法这门课#xff0c;但是有没有想过这门课到底是解决什么问题#xff1f;科学家设计这些数据结构和算法是要干嘛#xff1f;…这周主要总结了时间复杂度的学习跟小伙伴们分享下欢迎指正。一、为何需要分析算法复杂度挺多同学本科都学习过数据结构和算法这门课但是有没有想过这门课到底是解决什么问题科学家设计这些数据结构和算法是要干嘛其实最终的目的只有一个让我们写的代码在计算机上运行的速度更快使用的内存更省可是如何才能知道我们写的代码使用多少运行时间和内存呢这就需要分析算法时间复杂度和空间复杂度只有学会分析这 2 者才能知道我们设计的算法到底有没有性能的提升不然你费了很大功夫想了一个算法却发现运行速度慢如乌龟得不偿失。如果能够在运行算法之前就能知道算法大概的执行时间那就好了而复杂度分析恰好可以解决这个问题复杂度分析又分为 2 种1.1 运行后分析这种就是写完算法直接放到机器上面跑统计下到底用了多少时间和内存但是这种方法有 2 个缺点测试结果依赖运行机器性能强的机器当然需要的时间少测试结果依赖于测试用的数据比如对无序的数组和有序的数组排序的时间大不相同1.2 运行前分析那既然运行后分析有不可避免的缺点有没有办法在纸上提前计算一下算法大概的执行时间和内存用量呢当然有就是今天的主角大 O 复杂度表示法二、大 O 复杂度表示法我用一个例子来一步步解释大 O 复杂度表示法到底是什么意思int cal(int n) {int sum 0;int i 1;int j 1;for (; i n; i) {j 1;for (; j n; j) {sum sum i * j;}}}
对 CPU 而言执行程序分为以下 3 步读如代码指令和数据计算输出数据因为我们只是在运行前粗略地估计算法的运行时间因此可以假设每行代码在 CPU 上运行的时间都相同为 cputime那么我们就可以直接计算出上面函数中所有代码执行的总时间次数 x 单位时间n 表示输入数据的规模第 2、3、4 行每行需要 1 个 cpu_time共 第 5、6 行因为都是循环 n 次所以需要 第 7、8 行因为内外一共有 2 层 n 次的循环所以需要 那么总的运行时间 T(n) 为对于每个确定的算法所有代码的执行次数一定那么上面的 T(n) 与所有代码的执行次数 成正比关系比例系数就是 CPU 执行每行代码的时间 cputime因为可以把上式写成大 O 复杂度表示法其中T(n)表示算法执行的总时间f(n)表示算法总的执行次数就是 O()表示 T(n) 与 f(n) 的正比关系也就是大 O 的由来所以上面函数的总的执行时间又可以写成但是要注意大 O 复杂度表示法并不是计算代码准确的运行时间而是表示一种代码执行时间随着数据规模 n 增长的变化趋势记住不是准确的时间只是一种趋势而已因为实际工作的算法可能需要接受很大量级的数据通过分析算法运行时间与输入数据规模的变化趋势就能大概知道一个算法能不能在实际环境中很好的工作。但是呢上面的大 O 表示法还是不够简洁比如当算法代码很多的时候那我们是不是要在后面或者前面加上很多项这也不方便因此大佬们又想了方法** 只需要保留最大量级的运行次数即可** 这是因为当输入数据规模很大比如 100000 1000000 等常数项 3、一阶项 2n 等低阶的运行次数对最高次项 的影响并不大所有代码的运行次数基本与最高阶 的运行次数保持一致。因此我们只需要保留最高阶的运行次数就行并且系数也可以去掉因为我们表示的是变化趋势常量系数并不影响变化趋势这样最终的大 O 复杂度表示法就成型了这里之所以写的那么详细是因为这个复杂度分析真的非常重要因为我们只把算法写出来还不够我们还要能够分析算法的优劣并且以后的工作中如果需要选择数据结构来完成指定的功能你也必须要提前考虑自己选择的数据结构的运行时间这是非常重要的你做的不是玩具而是要能给用户提供体验良好的产品。三、时间复杂度分析学完大 O 表示法后分析时间空间复杂度就很容易了就是把前面的推导过程在不同的算法上计算一下不过常见的复杂度分析分为这 3 种。3.1 只分析循环次数最多的一段代码前面说过大 O 表示法只需要关注最高阶运行次数而在实际的代码中最高阶运行次数的代码往往是嵌套循环的最内层代码也就是循环执行次数最多的一段代码这种情况我们就只需要分析它就可以int cal(int n) {int sum 0;int i 1;for (; i n; i) {sum sum i;}return sum;}
可以发现执行次数最多的代码是 sum sum i利用前面的大 O 分析法很容易得出 T(n) O(n)3.2 加法法则加入我们的程序有 2 个单层的 n 次 for 循环还有一个 2 层的 n x n 的 for 循环注意这里每个循环的数据规模是一样的都是 n必须保证这一点int cal(int n) {int sum_1 0;int p 1;for (; p 100; p) {sum_1 sum_1 p;}int sum_2 0;int q 1;for (; q n; q) {sum_2 sum_2 q;}int sum_3 0;int i 1;int j 1;for (; i n; i) {j 1; for (; j n; j) {sum_3 sum_3 i * j;}}return sum_1 sum_2 sum_3;}
这种情况下我们只需要分别求出每个 for 的时间复杂度然后加起来取最大的量级就行总的 T(n)因为我们取最大量级所以如果忽略数据规模 n 的特殊情况我们可以取上面 3 个复杂度的最大值为最终结果上面算法最终的时间复杂度即为 加法法则一般的公式如下就是上面过程的一般情况只不过用数学化的表示而已很容易理解3.3 乘法法则类比加法法则乘法法则就很好理解加法是相加乘法就是多个复杂度相乘体现在代码中就是有多个嵌套的循环调用比如int cal(int n) {int ret 0; int i 1;for (; i n; i) {ret ret f(i);} } int f(int n) {int sum 0;int i 1;for (; i n; i) {sum sum i;} return sum;}
在 cal 函数的循环中每次都调用 f 函数来计算所以总的时间复杂度是这两个函数的乘积注意不同与加法乘法法则不是取最大的量级而是直接幂次累加要注意这点常用的时间复杂度Google 王争总结的几乎所有的复杂度如下图相信你应该听过 28 法则20% 的技术能解决 80% 的问题同样对复杂度分析工作中常用就如下几个O(1)代码中不含有循环、递归外的代码执行时间都为 O (1)记住 O (1) 并不是表示所有代码只执行一次而是表示这些代码的执行次数不会随着输入数据规模 n 的变化而变化即变化趋势是一个常量int i 8;
int j 6;
int sum i j;
不管有多少行上面这样的代码他们的时间复杂度都是 O(1)。O(logn), O(nlogn)这两种称为对数阶复杂度在排序算法中比较常见比如归并排序快速排序的复杂度都是 O(nlogn)但是这种复杂度分析相对难一点看个例子i1;
while (i n) {i i * 2;
}
这段代码的复杂度就是分析 i i * 2 的执行次数只要求出执行次数就搞定了学过等比数列的很容易看出所以当求出x log2(n)则时间复杂度就是 O (log2n)依葫芦画瓢i 1;
while (i n) {i i * 3;
}
同理 x log3(n)复杂度为 O (log3n)但是如果有很多不同的代码是不是都要改变底数呢并不用因为对数有个换底公式可以把一个对数换成指定的底数比如其中 是常数因为大 O 表示法可以省略系数所以可以看出 求出的复杂度也可以表示为 所以我们 统一忽略对数阶的底数都表示为 那么对于 就很好理解了就是利用乘法法则把 复杂度的代码执行 n 次即可。O(m n), O(m * n)这种复杂度有 2 个输入数据规模 m 和 n这表示我们的算法接收 2 个数据的输入但是因为数据规模不一定相同所以不能简单的利用加法法则int cal(int m, int n) {int sum_1 0;int i 1;for (; i m; i) {sum_1 sum_1 i;}int sum_2 0;int j 1;for (; j n; j) {sum_2 sum_2 j;}return sum_1 sum_2;
}
这种情况下不能取最大的量级因为数据规模不一样我们只需要做复杂度的相加即可T(n) O(m n)一般性的公式如下T1(m) T2(n) O[f(m) g(n)]
但乘法规则仍然有效如果两个嵌套循环的数据规模不同也成立for (int i 0; i m; i)for (int j 0; j n; j)...T1(m) * T2(n) O[f(m) * g(n)]
四、空间复杂度分析与时间复杂度类似渐进空间复杂度表示的是算法的存储空间随着数据规模变化的趋势空间复杂度分析比较容易void print(int n) {int i 0;int[] a new int[n];for (i; i n; i) {a[i] i * i;}for (i n-1; i 0; --i) {print out a[i]}
}
比如第二行申请的 int 内存与数据规模 n 无关空间复杂度为 O (1) 第三行申请的 int 数组内存与数据规模有关规模越大申请的内存就越多空间复杂度为 O (n)所以根据大 O 表示法最终的空间复杂度就是 O(n)常用的空间复杂有空间复杂度分析比较简单只需要看看有没有与数据规模相关的内存申请操作即可我们的重点还是放在时间复杂度分析不管是面试还是考试时间复杂度都是必定会问到的。五、不同情况下的复杂度分析除了以上各种情况的复杂度分析外还需知道不同情况下的复杂度主要分为 4 种情况最好、最坏平均均摊下面简单总结下都挺好理解的。5.1 最好、最坏情况时间复杂度比如这个例子在数组中查找元素 x 并返回索引// n 表示数组 array 的长度
int find(int[] array, int n, int x) {int i 0;int pos -1;for (; i n; i) {if (array[i] x) {pos i;break;}}return pos;
}
假如要查找的元素 X 是数组的第一个元素那么我们只需要循环一次就可以结束算法此时的时间复杂度为 O (1)也即最好情况时间复杂度但是假如我们要查找的元素 x 不在数组中那么我们就需要循环 n 次结束算法此时的时间复杂度为 O (n)对应的是最坏情况时间复杂度。5.2 平均情况时间复杂度通常情况下最好或者最坏时间复杂度情况发生的概率不大所以为了表示一般情况下的复杂度我们使用平均情况时间复杂度这种情况需要简单的计算不过很容易还以上面的例子// n 表示数组 array 的长度
int find(int[] array, int n, int x) {int i 0;int pos -1;for (; i n; i) {if (array[i] x) {pos i;break;}}return pos;
}
因为是平均情况所以可以做个假设假设要查找的变量 x在数组中的概率为 1/2不在数组中的概率也为 1/2出现在 0 - n-1 这 n 个数组位置的概率相同即为 1/n所以根据概率乘法要查找的数据 x 出现在数组中的任意位置的概率为 1/2n先出现在数组中的概率乘以任意位置的概率然后我们就可以将每个元素被找到时要查找的次数和对应概率相乘最后再相加就得到算法的平均时间复杂度简单解释下1 x 1/2n 表示数组第一个元素只需要循环查找一次n x 1/2n 表示数组最后一个元素需要循环查找 n 次n x 1/2 表示不在数组中的元素也需要查找 n 次因为你必须把数组元素都遍历完后才能知道当前要查找的 x 不在数组中那肯定就在数组外面喽前面说过在数组外面的概率也是 1/2那么最后的结果就是全部想加因为可以省略系数所以上面查找元素 x 算法的时间复杂度也是 。虽然存在这 3 种情况但是实际工作中分析算法的时间复杂度时并不需要严格分析这 3 种不同情况。一般情况下使用前面讲的复杂度分析方法得出复杂度即可如果要详细推导的话可以计算下平均时间复杂度。5.3 均摊时间复杂度这是一种特殊情况下的复杂度并不是很常见但还是了解下它的主要思想是把运行时间多的情况下的复杂度拆分并均摊到运行时间少的情况下看个例子// array表示一个长度为n的数组
// 代码中的array.length就等于n
int[] array new int[n];
int count 0;void insert(int val) {if (count array.length) {int sum 0;for (int i 0; i array.length; i) {sum sum array[i];}array[0] sum;count 1;}array[count] val;count;
}
这个算法实现如下功能往数组中插入一个元素 val当数组满了后对数组求和并把结果放到数组第一个元素的位置上O (n) 当数组没满直接插入元素 val 到空闲的位置上O (1)利用前面学习的复杂度分析可以很容易知道这两种情况的时间复杂度分别为O(n) 和 O(1)但是考虑实际运行情况我们总是先把数组一个个位置存满 O (1)然后满了之后再执行求和的操作 O (n)并且这两种情况的发生是有规律的。因此我们可以把比较耗时 O (n) 复杂度的求和操作的均摊到不太耗时的 O (1) 插入操作上这样总体的时间复杂度就会变成 O (1)这就是均摊的思想总结下均摊时间复杂度的应用场景大多数情况 1 是不耗时的操作个别情况 2 是耗时操作情况 1 和情况 2 的操作在时间和逻辑上都是连续的有清晰的前后执行顺序就类似上面这个例子如果你工作中的算法满足这 3 个条件那么可以尝试用均摊时间复杂度来分析这种情况比较少见但还是要知道有这样一种类型。六、复杂度分析总结今天学习的时空复杂度分析是数据结构和算法学习中非常重要的一环只有学会分析时空复杂度我们才能知道自己写的算法到底能够提升多快如果不会分析复杂度那只会盲目地选择数据结构盲目地设计算法时间复杂度就是我们设计算法的指标。我们学习数据结构和算法的目的就是为了写出运行速度更快存储用量更低的代码如果都不会分析算法的执行时间和内存用量那最后何谈学过这门课或者学会这门课呢请务必重视复杂度分析后面设计算法会经常用到。OK大家下个专题见本文原创首发于微信公号「登龙」分享机器学习、算法编程、Python、机器人技术等原创文章扫码关注回复「1024」你懂的
