用dw软件做网站栅格系统,动画制作软件推荐,合肥大建设,wordpress邮箱美化图片来自 Pixabay#xff0c;作者#xff1a;TeroVesalainen2019 年第 74 篇文章#xff0c;总第 98 篇文章本文大约 3000 字#xff0c;阅读大约需要 10 分钟最近会开始更新一个数据结构算法的学习系列#xff0c;同时不定期更新 leetcode 的刷题。这是第一篇文章#x… 图片来自 Pixabay作者TeroVesalainen2019 年第 74 篇文章总第 98 篇文章本文大约 3000 字阅读大约需要 10 分钟最近会开始更新一个数据结构算法的学习系列同时不定期更新 leetcode 的刷题。这是第一篇文章在开始介绍各种数据结构和算法之前先了解下什么是复杂度包括时间复杂度和空间复杂度。今日推荐阅读精心挑选了这些牛人的公众号来看看吧什么是复杂度分析数据结构和算法解决是“如何让计算机更快时间、更省空间的解决问题”。因此需从执行时间和占用空间两个维度来评估数据结构和算法的性能。分别用时间复杂度和空间复杂度两个概念来描述性能问题二者统称为复杂度。复杂度描述的是算法执行时间或占用空间与数据规模的增长关系。为什么需要复杂度分析和性能测试相比复杂度分析有不依赖执行环境、成本低、效率高、易操作、指导性强的特点。掌握复杂度分析将能编写出性能更优的代码有利于降低系统开发和维护成本。如何进行复杂度分析对于时间复杂度的分析通常使用大O复杂度表示法表示代码执行时间随数据规模增长的变化趋势所以也叫作渐进时间复杂度asymptotic time complexity简称时间复杂度。用公式表示就是 T(n) O(f(n))表示其中 T(n) 表示算法执行总时间f(n) 表示每行代码执行总次数而 n 表示数据的规模。由于时间复杂度描述的是算法执行时间与数据规模的增长变化趋势所以常量阶、低阶以及系数实际上对这种增长趋势不产决定性影响所以在做时间复杂度分析时可以忽略这些项。具体分析的时候有下列三个方法单段代码只看循环次数最多的部分多段代码取复杂度最高的即有个多个循环但只看循环次数量级最高的那段代码乘法法则--嵌套代码进行乘积多个循环嵌套就是相乘常见的时间复杂度按照数量级递增常见的时间复杂度量级有常量阶 O(1)对数阶 O(logn)线性阶 O(n)线性对数阶 O(nlogn)平方阶 O(n^2)立方阶 O(n^3)…k次阶 O(n^k)指数阶 O(2^n)阶乘阶 O(n!)其中最后两种情况是非常糟糕的情况当然 O(n^2) 也是一个可以继续进行优化的情况。接下来简单介绍上述复杂度中的几种比较常见的O(1)O(1) 表示的是常量级时间复杂度也就是只要代码的执行时间不随 n 的增大而增长都记作 O(1) 。一般只要算法不包含循环语句和递归语句时间复杂度都是 O(1)像下列代码有 3 行但时间复杂度依然是O(1)而非 O(3)。a 3
b 4
print(a b)
O(logn)、O(nlogn)O(logn) 也是一个常见的时间复杂度下面是一个 O(logn) 的代码例子i 1
count 0
n 20
while i n:count 1i * 2
print(while 循环运行了 {} 次.format(count))
这段代码其实就是每次循环都让变量 i 乘以 2直到其大于等于 n这里我设置 n20然后运行了后输出结果是循环运行了 5 次。实际上这段代码的结束条件就是求 2^xn 中的 x 是等于多少那么循环次数也就知道了而求 x 的数值方法就是 那么时间复杂度就是 假如上述代码进行简单的修改将 i * 2 修改为 i * 3 那么同理可以得到时间复杂度就是 。但在这里无论是以哪个为对数的底我们都把对数阶的时间复杂度记为 O(logn)。这里主要原因有两个对数可以互换比如 也就是 常量基于前面的理论系数可以被忽略也就是这里的常量 C 可以忽略基于这两个原因对数阶的时间复杂度都忽略了底统一为 O(logn) 。至于 O(nlogn) 根据乘法法则只需要将对数阶复杂度的代码运行 n 次就可以得到这个线性对数阶复杂度了。注意 O(nlogn) 是非常常见的时间复杂度常用的排序算法如归并排序、快速排序的时间复杂度都是 O(nlogn)O(mn)、O(m*n)前面介绍的情况都是只有一个数据规模 n 但这里介绍有两个数据规模的情况--m和 n。# O(mn)
def cal(n, m):result 0for i in range(n):result ifor j in range(m):result j * 2return result
简单的代码示例如上述所示如果事先无法评估 m 和 n 的量级大小那么这里的时间复杂度就没法选择量级最大的所以其时间复杂度就是 O(mn) 。同理对于嵌套循环就是 O(m*n) 的时间复杂度了。最好、最坏、平均、均摊时间复杂度这四种复杂度的定义如下最好情况时间复杂度代码在最理想的情况下执行的时间复杂度最坏情况时间复杂度代码在最坏情况下执行的时间复杂度平均情况时间复杂度代码在所有情况下执行的次数的加权平均值表示均摊时间复杂度代码执行的所有复杂度情况中绝大多数都是低级别的复杂度个别情况会发生最高级别复杂度且发生具有时序关系时可以将个别高级别复杂度均摊到低级别复杂度上。基本上均摊复杂度就等于低级别复杂度也可以看作是特殊的平均时间复杂度。为什么会有这四种复杂度呢原因是同一段代码在不同情况下时间复杂度会出现量级差异为了更全面、更准确描述代码的时间复杂度引入这四种复杂度的概念但通常除非代码是出现量级差别的时间复杂度才需要区分这四种复杂度大多数情况都不需要区分它们。下面是给出第一个代码例子# 在数组 arr 中查找目标数值 x
def find(arr, x):for val in arr:if val x:return Truereturn False
这个例子假设数组 arr 的长度是 n 那么它最好的情况就是第一个数值就是需要查找的 x 此时复杂度是 O(1) 但最坏情况就是最后一个数值或者不存在需要查找的 x 那么此时就遍历一遍数组复杂度就是 O(n) 因此这段代码最好和最坏情况是会出现量级差别的O(1) 和 O(n) 分别是最好情况复杂度和最坏情况复杂度。而这段代码的平均情况时间复杂度是 O(n) 具体分析就是首先考虑所有可能的情况以及对应出现的概率可能发生的情况先分为两种存在和不存在需要查找的数值 x也就是分别是 1/2 的概率然后对于存在的情况下又有 n 种情况即出现在数组任意位置的概率都是均等的那么它们的概率乘以存在的概率就是 1/2n 接着再考虑每种情况需要搜索的元素个数其实就是代码执行的次数这个分别就是从 1 到 n并且对于不存在的情况也是 n 需要遍历一遍数组才发现不存在所以平均时间复杂度的计算过程如下加权平均值也叫期望值所以平均时间复杂度的全称应该叫加权平均时间复杂度或者期望时间复杂度。这里用大 O 表示法表示并且去掉常量和系数后就是 O(n)。最后介绍下均摊时间复杂度需要满足以下两个条件才使用1代码在绝大多数情况下是低级别复杂度只有极少数情况是高级别复杂度2低级别和高级别复杂度出现具有时序规律。均摊结果一般都等于低级别复杂度。空间复杂度分析和时间复杂度的定义类似空间复杂度全称就是渐进空间复杂度(asymptotic space complexity)表示算法的存储空间与数据规模之间的增长关系。简单介绍下一个程序所需要的空间主要由以下几个部分构成指令空间是值用来存储经过编译之后的程序指令所需要的空间。数据空间是指用来存储所有常量和变量值所需的空间。其主要由两个部分构成存储常量和简单变量所需要的空间存储复合变量所需要的空间。这一类空间包括数据结构所需要的动态分配的空间环境栈空间用来保存函数调用返回时恢复运行所需要的信息。例如如果函数 fun1 调用了函数 fun2那么至少必须保存 fun2 结束时 fun1 将要继续执行的指令的地址。本系列主要参考极客时间上的数据结构与算法之美课程目前这门课正在做活动拼团只需 65 元课程的设计非常合理而且介绍得很详细有对应的代码辅助理解还有一个开源的 GitHub目前已经有1w的star了https://github.com/wangzheng0822/algo欢迎关注我的微信公众号--算法猿的成长或者扫描下方的二维码大家一起交流学习和进步如果觉得不错在看、转发就是对小编的一个支持
