在任何情况下,您是否更喜欢O(log n)时间复杂度和O(1)时间复杂度？或O(n)到O(log n)？
你有什么例子吗？
可能有许多理由偏好具有较高O时间复杂度的算法而不是较低的算法:
大多数时候,较低的大O复杂度难以实现,需要熟练的实现,大量的知识和大量的测试.
big-O隐藏了一个常量的细节:10^5从大O角度来看,执行的算法比1/10^5 * log(n)(O(1)vs O(log(n))n更好,但是对于最合理的,第一个算法会表现得更好.例如,矩阵乘法的最佳复杂度是O(n^2.373)常数是如此之高,以至于没有(据我所知)计算库使用它.
当你计算一些大的东西时,big-O是有意义的.如果你需要对三个数字的数组进行排序,那么无论你使用O(n*log(n))还是O(n^2)算法都很重要.
有时,小写时间复杂度的优势可以忽略不计.对于例如有一个数据结构探戈树这给出了一个O(log log N)时间复杂度找到一个项目,但也有其发现在同一个二叉树O(log n).即使对于大量n = 10^20的差异也可以忽略不计.
时间复杂性不是万能的.想象一下运行在O(n^2)并需要O(n^2)内存的算法.当n不是很大时,它可能比O(n^3)时间和O(1)空间更好.问题是你可以等待很长时间,但是我很怀疑你能找到一个足够大的RAM来与你的算法一起使用它
并行化是我们分布式世界的一个很好的特性.有些算法很容易并行化,有些算法根本没有并行化.有时,在1000台商用机器上运行算法比使用复杂性略高的一台机器更复杂.
在某些地方(安全),复杂性可能是必需的.没有人想要一个可以快速散列的哈希算法(因为那时其他人可以更快地强制你)
虽然这与切换复杂性无关,但是应该以防止定时攻击的方式编写一些安全功能.它们大多数都停留在相同的复杂性类别中,但是以一种总是需要更糟糕的方式进行修改.一个例子是比较字符串是否相等.在大多数应用程序中,如果第一个字节不同,则快速突破是有意义的,但在安全性方面,您仍将等待最终告诉坏消息.
有人为低复杂度算法申请了专利,对于公司来说,使用更高的复杂性而不是付钱更为经济.
一些算法很好地适应特定情况.插入排序,例如,具有的平均时间复杂度O(n^2),比快速排序或归并差,但作为一个在线算法,因为它们被接收(作为用户输入),其中大多数其他算法只能有效地操作它可以有效地排序的值的列表在完整的值列表上.
总有隐藏的常量,在O(log n)算法上可以更低.因此,它可以更快地在实际中用于实际数据.
还存在空间问题(例如在烤面包机上运行).
还有开发人员时间问题 - O(log n)可能更容易实现和验证1000.
我很惊讶没有人提到过内存限制的应用程序.
由于其复杂性(即O(1)< O(log n))或者因为复杂性前面的常数较小(即2 n 2 <6 n 2),可能存在具有较少浮点运算的算法.无论如何,如果较低的FLOP算法更受内存限制,您可能仍然更喜欢具有更多FLOP的算法.
我所说的"内存限制"是指您经常访问经常超出缓存的数据.为了获取此数据,您必须先将实际内存空间中的内存提取到缓存中,然后才能对其执行操作.这个提取步骤通常非常慢 - 比您的操作本身慢得多.
因此,如果您的算法需要更多操作(但这些操作是在已经在缓存中的数据上执行的[因此不需要提取]),它仍然会以较少的操作(必须在外部执行)执行算法. -cache数据[因此需要获取])在实际的壁时间方面.
在数据安全性受到关注的情况下,如果更复杂的算法具有更好的抗时间攻击性,则更复杂的算法可能优于不太复杂的算法.
Alistra钉了它,但没有提供任何例子,所以我会.
您有一个10,000个UPC代码列表,用于商店销售的商品代码.10位UPC,价格整数(便士价格)和收据描述的30个字符.
O(log N)方法:您有一个排序列表.如果是ASCII则为44字节,如果是Unicode则为84 或者,将UPC视为int64,得到42和72字节.10,000条记录 - 在最高的情况下,您看起来有点不到一兆字节的存储空间.
O(1)方法:不存储UPC,而是将其用作数组的入口.在最低的情况下,您正在查看几乎三分之一的TB存储空间.
您使用哪种方法取决于您的硬件.在大多数任何合理的现代配置中,您将使用log N方法.我可以想象第二种方法是正确的答案,如果由于某种原因你在一个RAM很短但你有大量存储空间的环境中运行.磁盘上三分之一的TB是没什么大不了的,在磁盘的一个探针中获取数据是值得的.简单的二进制方法平均需要13个.(但请注意,通过对键进行聚类,您可以将其保证为3次读取,实际上您将缓存第一个.)
考虑一棵红黑树.它具有访问,搜索,插入和删除功能O(log n).与数组进行比较,该数组具有访问权限O(1)和其余操作O(n).
因此,给定一个应用程序,我们插入,删除或搜索比我们访问更频繁,并且只在这两个结构之间进行选择,我们更喜欢红黑树.在这种情况下,您可能会说我们更喜欢红黑树更加繁琐的O(log n)访问时间.
为什么？因为访问不是我们最重要的考虑因素.我们正在进行权衡:我们的应用程序的性能受到除此之外的因素的更大影响.我们允许这种特定算法遭受性能,因为我们通过优化其他算法来获得大量增益.
因此,您的问题的答案就是:当算法的增长率不是我们想要优化的时候,当我们想要优化其他东西时.所有其他答案都是特殊情况.有时我们会优化其他操作的运行时间.有时我们会优化内存.有时我们会优化安全性.有时我们会优化可维护性.有时我们会优化开发时间.当您知道算法的增长率对运行时间的影响不是最大时,即使最重要的常数足够低也可以优化运行时间.(如果您的数据集超出此范围,您将优化算法的增长率,因为它最终将主导常量.)一切都有成本,在许多情况下,我们交易的成本更高的成本算法优化别的东西.
是.
在实际情况中,我们使用短字符串键和长字符串键进行了一些表查找.
我们使用a std::map,a std::unordered_map,哈希,在字符串的长度上最多采样10次(我们的键往往是guid,所以这很不错),并且哈希对每个字符进行采样(理论上减少了冲突),一个未排序的向量,我们进行==比较,并且(如果我没记错的话)一个未排序的向量,我们也存储一个哈希,首先比较哈希,然后比较字符.
这些算法的范围从O(1)(unordered_map)到O(n)(线性搜索).
对于适度大小的N,通常O(n)击败O(1).我们怀疑这是因为基于节点的容器需要我们的计算机更多地在内存中跳转,而基于线性的容器则没有.
O(lg n)存在于两者之间.我不记得它是怎么做的.
性能差异并不大,在较大的数据集上,基于散列的数据集表现得更好.所以我们坚持使用基于散列的无序映射.
在实践中,对于合理大小的n,O(lg n)是O(1).如果您的计算机在您的表中只有40亿个条目的空间,那么O(lg n)就在上面32.(lg(2 ^ 32)= 32)(在计算机科学中,lg是基于日志的简写2).
在实践中,lg(n)算法比O(1)算法慢,不是因为对数增长因子,而是因为lg(n)部分通常意味着算法存在一定程度的复杂性,并且复杂性增加了比lg(n)项中的任何"增长"更大的常数因子.
但是,复杂的O(1)算法(如哈希映射)很容易产生类似或更大的常数因子.
并行执行算法的可能性.
我不知道如果有一个类的实例O(log n)和O(1),但对于一些问题,你选择的算法具有较高的复杂类时,算法很容易并行执行.
有些算法不能并行化,但复杂度很低.考虑另一种算法,该算法可以实现相同的结果并且可以轻松并行化,但具有更高的复杂性等级.在一台机器上执行时,第二种算法较慢,但在多台机器上执行时,实际执行时间越来越低,而第一种算法无法加速.
假设您正在嵌入式系统上实施黑名单,其中0到1,000,000之间的数字可能会被列入黑名单.这留下了两个可能的选择:
使用1,000,000位的位集
使用已列入黑名单的排序数组,并使用二进制搜索来访问它们
访问bitset将保证持续访问.就时间复杂性而言,它是最佳的.从理论和实际的角度来看(O(1)具有极低的恒定开销).
不过,您可能希望更喜欢第二种解决方案.特别是如果你希望黑名单整数的数量非常小,因为它会更有效.
即使你没有为内存稀缺的嵌入式系统开发,我也可以增加1,000,000到1,000,000,000,000的任意限制,并提出相同的论点.然后bitset将需要大约125G的内存.保证O(1)的最坏情况复杂性可能无法说服你的老板为你提供如此强大的服务器.
在这里,我强烈希望在O(1)位集上进行二进制搜索(O(log n))或二叉树(O(log n)).而且,最糟糕的O(n)复杂度的散列表可能会在实践中击败所有这些.
我在这里的答案随机矩阵的所有行的快速随机加权选择是一个例子,其中复杂度为O(m)的算法比复杂度为O(log(m))的算法快,m而不是太大.
人们已经回答了你的确切问题,所以我会解决一个人们在来这里时可能会想到的一个稍微不同的问题.
许多"O(1)时间"算法和数据结构实际上只占用预期的 O(1)时间,这意味着它们的平均运行时间为O(1),可能仅在某些假设下.
常见示例:哈希表,"数组列表"的扩展(也称为动态大小的数组/向量).
在这种情况下,您可能更喜欢使用数据结构或算法,其时间保证以对数方式绝对限制,即使它们的平均性能可能更差.
因此,一个示例可能是平衡的二叉搜索树,其运行时间平均更差,但在最坏的情况下更好.
一个更普遍的问题是,如果有其中一个希望的情况下,O(f(n))算法的O(g(n)),即使算法g(n) << f(n)是n趋于无穷大.正如其他人已经提到的那样,在f(n) = log(n)和的情况下答案显然是"是" g(n) = 1.即使在f(n)多项式但是g(n)指数的情况下,有时也是如此.一个着名而重要的例子是用于解决线性规划问题的单纯形算法.在20世纪70年代,它被证明是O(2^n).因此,其糟糕的行为是不可行的.但是 - 它的平均案例行为非常好,即使对于成千上万个变量和约束的实际问题也是如此.在20世纪80年代,人们发现了用于线性规划的多项式时间算法(例如Karmarkar的内点算法),但30年后,单纯形算法似乎仍然是首选算法(除了某些非常大的问题).这是显而易见的原因,平均情况行为通常比最坏情况行为更重要,但也有一个更微妙的原因,即单纯形算法在某种意义上更具信息性(例如灵敏度信息更容易提取).
把我的2美分投入:
当算法在某个硬件环境上运行时,有时会选择更复杂的算法来代替更好的算法.假设我们的O(1)算法非顺序地访问一个非常大的固定大小数组的每个元素来解决我们的问题.然后将该阵列放在机械硬盘驱动器或磁带上.
在这种情况下,O(logn)算法(假设它顺序访问磁盘)变得更有利.
使用O(log(n))算法代替O(1)算法有一个很好的用例,许多其他答案都忽略了这种算法:不变性.哈希映射具有O(1)个put和gets,假设哈希值的分布很好,但它们需要可变状态.不可变树映射具有O(log(n))puts和gets,它渐近地变慢.但是,不变性可能足以弥补性能的下降,并且在需要保留多个版本的映射的情况下,不变性允许您避免必须复制映射,即O(n),因此可以改进性能.
简单地说:因为系数 - 与设置,存储和该步骤的执行时间相关的成本 - 可以通过较小的大O问题比使用较大的问题大得多.Big-O只是算法可扩展性的衡量标准.
考虑以下来自Hacker's Dictionary的例子,提出一种依赖于量子力学的多世界解释的排序算法:
使用量子过程随机置换数组,
如果数组未排序,则销毁Universe.
所有剩余的宇宙现在都已排序[包括您所在的宇宙].
(来源:http://catb.org/~esr/jargon/html/B/bogo-sort.html)
请注意,此算法的big-O O(n)胜过通用项目迄今已知的任何排序算法.线性步长的系数也非常低(因为它只是比较,而不是交换,线性完成).事实上,类似的算法可用于在多项式时间内解决NP和co-NP中的任何问题,因为可以使用量子过程生成每个可能的解决方案(或可能证明没有解决方案),然后在多项式时间.
但是,在大多数情况下,我们可能不希望承担多个世界可能不正确的风险,更不用说执行第2步的行为仍然"留给读者".
在n有界并且O(1)算法的常数乘数高于log(n)上的界限时的任何点. 例如,将值存储在散列集中是O(1),但可能需要昂贵的散列函数计算.如果可以简单地比较数据项(关于某个顺序)并且n上的边界使得log n明显小于任何一个项上的散列计算,那么存储在平衡二叉树中可能比存储在一个哈希集.
在你需要一个坚定的上限的实时情况下,你会选择一个heapsort而不是一个Quicksort,因为heapsort的平均行为也是最糟糕的行为.
添加到已经很好的答案.一个实际的例子是postgres数据库中的哈希索引与B树索引.
哈希索引形成哈希表索引以访问磁盘上的数据,而btree顾名思义使用Btree数据结构.
在Big-O时间,这些是O(1)vs O(logN).
散列索引目前Postgres里,因为在特别是在数据库系统中的真实生活状况气馁,不发生碰撞的实现哈希是非常困难(可能导致O(N)最坏情况的复杂性)和正因为如此,它更是困难,使他们崩溃安全(称为提前写入记录 - 在postgres中的WAL).
这种权衡是在这种情况下进行的,因为O(logN)对索引来说足够好并且实现O(1)非常困难并且时间差异并不重要.
京公网安备 11010802040832号 | 京ICP备19059560号-6 