大O表示法的工作原理-用Cake解释

2020年12月30日10:40:42 发表评论 36 次浏览

本文概述

Big O表示法在计算机科学中用于定义算法的上限。它主要用于根据输入大小来定义算法的最大时间, 但是也可以用于定义内存使用情况。

在本文中, 我们将使用生日蛋糕来说明最常见的"大O"符号类型。我们将假装自己举办一个派对, 并需要根据参加人数来确定要烘焙多少蛋糕。

O(1)-恒定时间

对于"恒定时间"示例, 无论有多少人参加生日聚会, 你都只会做一个蛋糕。因此, 蛋糕制作时间保持不变。

0(1)恒定时间图示

请注意, Big O表示法并未指定"恒定时间"的持续时间(制作蛋糕可能需要1个小时, 可能需要4个小时)。它只是说花费的时间并没有随着客人数量的增加而增加。

O(1)操作的真实示例是通过其索引访问数组。从10个项目数组中检索元素就像从100万个项目数组中检索元素一样快。

0(1)恒定时间图

O(log n)-对数时间

对于对数时间示例, 生日蛋糕被用作激励人们准时参加聚会的一种方式。

第一个到达的人给自己一个蛋糕。然后, 接下来的2个人到达共享蛋糕。然后接下来的4个人共享一个蛋糕, 依此类推。

因此, 一个1人聚会需要1个蛋糕。 2至3人的聚会需要2个蛋糕。一个4至7人的聚会需要3个蛋糕, 而一个8至15人的聚会需要4个蛋糕。通常, " n人"聚会需要登录2(n)蛋糕。

O(log n)对数时间图

现实世界中最常见的O(log n)操作示例是对有序数组的二进制搜索。

该算法查看数组的中间位置, 并查看该值是低于还是高于其要查找的值。由于列表是有序的, 因此它知道目标值位于数组的哪一半。

然后, 对阵列的那一半重复该过程。因此, 对于16个项目的数组, 第一次迭代将搜索范围缩小到8个项目, 然后依次是4、2、1, 最大为4, 或者2(16), 遍历所有对象。

O(log n)对数时间图

O(n)-线性时间

对于线性时间示例, 每个客人都有自己的蛋糕。如果有'n'人参加聚会, 则需要制作'n'蛋糕。因此, 花费的时间与客人人数有关。

O(n)线性时间图

同样, Big O表示法没有指定时间有多长(可能要花1个小时做蛋糕, 也许要花4个小时), 只是说明时间随客人人数呈线性增加。

O(n)操作的真实示例是对数组中项目的天真的搜索。在10个项目的数组中, 最坏的情况是你必须查看所有10个项目才能找到所需的项目。但是对于一百万个项目的阵列, 你可能必须查看全部一百万个项目。

当然, 你可能会更快找到解决方案, 但是Big O表示法指定算法将花费的最长时间。

O(n)线性时间图

O(n ^ 2)-二次时间

对于"二次方时间"示例, 每个来宾都有自己的蛋糕。此外, 每个蛋糕上都写有所有客人的名字, 并有一些美味的糖衣。

在这种情况下, 一个1人聚会上有一个蛋糕, 上面有一个名字。一个2人的聚会有两个蛋糕, 每个蛋糕上都有两个名字(总共4个名字), 而一个3人的聚会有三个蛋糕, 每个蛋糕上都带有三个名字的名字, 总共9个名字。

O(n ^ 2)二次时间图

通常, " n"个人聚会需要写下n * n个名字(也称为n平方, 或者n等于2的幂), 因此制作蛋糕(和写下所有名字)的速度与访客人数的平方。

O(n ^ 2)操作的真实示例是对数组中重复项的幼稚搜索。在这种情况下, 你将遍历数组中的所有项目, 对于每个这些项目, 请再次遍历数组以查看是否存在任何匹配项。

对于10个项目的数组, 外循环有10次迭代, 而对于每个循环, 内循环有10次迭代, 总共100次。对于一百万个项目的数组, 它是一万亿个。

O(n ^ 2)有一个更一般的情况, 其中时间不是相对于n的2的幂(n ^ 2), 而是相对于n的c的幂(n ^ c)。这通常称为多项式时间。

O(n ^ 2)二次时间图

O(n!)-析因时间

对于析因时间示例, 来宾参加了皮坦克比赛, 冠军将蛋糕带回家。

但是, 存在一个小问题, 即首轮比赛的玩家处于劣势。为了帮助解决问题, 我们玩了很多游戏, 以便涵盖客人的每个排列, 每个人都可以先走。所有这些排列都写在蛋糕上, 再加上一些美味的糖衣。

这意味着一个2人聚会有两个游戏, 因为每个客人依次轮流参加。一个3人的聚会有6场比赛(如果我们假设客人是Anna, Brian和Chris, 则排列的是ABC, ACB, BAC, BCA, CAB, CBA)。

O(n!)-析因时间图

通常, " n人"派对需要n!或n个阶乘游戏, 因此制作蛋糕的速度与此相关。

n!通过将所有整数从n乘以一个" n *(n-1)*(n-2)…* 2 * 1"来计算。因此, 对于2人聚会, 它是2 * 1或2。对于三人聚会, 它是3 * 2 * 1, 即6。

O(n!)操作的真实示例是需要分析排列列表的任何事物, 例如旅行商问题.

O(n!)阶乘时间图

结论

希望生日蛋糕能使" Big O"符号更容易理解!下图也是一个很好的记忆辅助, 显示了算法的相对速度(如果有选择, 那么你想要更快的算法!)

大O符号图

还有很多其他的" Big O"表示法, 例如O(n log n)和O(c ^ n), 但它们都遵循相同的模式。你可以在大O维基百科页面, 以及数学证明和其他令人兴奋的细节。

一盏木

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: