标签: complexity-theory

O(n!)函数的示例(在代码中)是什么？应该参考n运行适当数量的操作; 也就是说,我在问时间的复杂性.

简介:
当学术(计算机科学)论文说"O(polylog(n))"时,它们是什么意思？我不会对"Big-Oh"符号感到困惑,我非常熟悉它,而是使用polylog(n)函数.他们不是在谈论我认为的复杂分析函数Li _s(Z).或者是他们？也许完全不同的东西？

更多细节:
主要是出于个人兴趣,我最近一直在查看关于压缩后缀阵列的各种论文,例如后向搜索的优点 - 高效的辅助内存和压缩后缀阵列的分布式实现.所述的计算复杂度估计有时涉及polylog(n),这是我不熟悉的函数.

维基百科给出了polylog _s(z)的定义,它似乎主要是关于复杂分析和解析数论.我怀疑它与压缩文件中的polylog(n)无关,尽管我更喜欢听到知识渊博的人的其他信息.如果是这种情况,为什么省略下标是否合理？

我唯一的猜测是,O(polylog(n))可能意味着"渐近于log(n)的多项式函数".但这只是一个猜测:我没有证据证明这一点,并且它会滥用记谱法来启动.

在任何情况下,非常感谢指向合理权威定义的链接!

是否有人能够提供一个"简单的英语"直观,但正式的解释是什么让QuickSort n登录？根据我的理解,它必须通过n个项目,并且它会记录n次...我不知道如何将其记入单词为什么它会执行此日志n次.

我已经看到,在大多数情况下,时间复杂度与空间复杂性有关,反之亦然.例如,在数组遍历中:

for i=1 to length(v)
    print (v[i])
endfor

这里很容易看出算法在时间上的复杂度是O(n),但在我看来,空间复杂度也是n(也表示为O(n)？).

我的问题:算法是否可能具有与空间复杂度不同的时间复杂度？

我已经注意到O(1)在讨论涉及散列和搜索类型的算法时的一些非常奇怪的用法,通常是在使用语言系统提供的字典类型的上下文中,或者使用使用数组使用的字典或散列数组类型 - 索引符号.

基本上,O(1)意味着以恒定时间和(通常)固定空间为界.一些非常基本的操作是O(1),尽管使用中间语言和特殊虚拟机往往会扭曲思考的人(例如,如何将垃圾收集器和其他动态过程分摊到O(1)活动之外).

但是忽略了延迟,垃圾收集等的摊销,我仍然不明白如何假设某些涉及某种搜索的技术可以是O(1),除非在非常特殊的条件下.

虽然我之前已经注意到这一点,但是在Pandincus问题中出现了一个例子,"'正确'集合用于在C#.NET中获取O(1)时间内的项目？" .

正如我在那里所说的那样,我所知道的唯一一个提供O(1)访问作为保证边界的集合是一个带有整数索引值的固定绑定数组.假设通过一些映射到随机存取存储器来实现该阵列,该存储器使用O(1)操作来定位具有该索引的单元.

对于涉及某种搜索以确定不同类型索引(或具有整数索引的稀疏数组)的匹配单元的位置的集合,生活并不那么容易.特别是,如果存在可能的碰撞和拥堵,则访问不完全是O(1).而如果集合是灵活的,必须认识和摊销扩大基础结构的成本(如树或哈希表),其纾缓交通挤塞(例如,高发病碰撞或树的不平衡).

我永远不会想到将这些灵活和动态的结构称为O(1).然而,我认为它们作为O(1)解决方案提供,而没有任何必须保持​​的条件,以确保实际上具有O(1)访问(以及使该常数可忽略地小).

问题:所有这些准备都是一个问题.O(1)的偶然性是什么？为什么这么盲目地被接受？是否认识到即使O(1)可能不合需要地大,即使接近常数？或者O(1)只是将计算复杂性概念挪用于非正式用途？我很困惑.

更新:答案和评论指出了我自己定义O(1)的习惯,我已经修复了.我仍然在寻找好的答案,在一些情况下,一些评论主题比他们的答案更有趣.

我今天在想什么可能是有史以来最复杂/最令人印象深刻的应用程序.所以我开始考虑我喜欢和使用日常数据库.

然后我进入了未知领域(对我们大多数人来说,我猜),政府.我只能想象NASA应用程序的复杂性,它们允许它们与火星上的流动站进行通信.

但后来我开始思考自从小时候以来我每天都在使用的东西,游戏.不是游戏开发者,这给我带来了大量关于人工智能和计算复杂性的问题,超出了我能想到的任何问题.

游戏是最复杂/令人印象深刻的应用吗？

快速提问主要是为了满足我对这个话题的好奇心.

我正在编写一些带有SQlite数据库后端的大型python程序,将来会处理大量的记录,所以我需要尽可能地进行优化.

对于一些函数,我在字典中搜索键.我一直在使用"in"关键字进行原型设计,并计划稍后返回并优化这些搜索,因为我知道"in"关键字通常是O(n)(因为这只是转换为python迭代整个列表并进行比较每个元素).但是,由于python dict基本上只是一个哈希映射,python解释器是否足够智能解释:

if(key in dict.keys()):
    ...code...

至:

if(dict[key] != None):
    ...code...

它基本上是相同的操作,但顶部是O(n),底部是O(1).

我很容易在我的代码中使用底部版本,但后来我只是好奇并且想我会问.

我不是新手使用正则表达式,我理解他们所基于的基本理论 - 有限状态机.

我不太擅长算法分析,也不理解正则表达式与基本线性搜索的比较.我问,因为从表面上看,它似乎是一个线性阵列搜索.(如果正则表达式很简单.)

我在哪里可以了解有关实现正则表达式引擎的更多信息？

我正在写一个看起来像这样的python函数

def foo(some_list):
   for i in range(0, len(some_list)):
       bar(some_list[i], i)

所以它被称为

x = [0, 1, 2, 3, ... ]
foo(x)

我曾经假设列表的索引访问是O(1),但是很惊讶地发现,对于大型列表,这比我预期的要慢得多.

那么,我的问题是如何实现python列表,以及下面的运行时复杂性是什么

• 索引: list[x]
• 从最后弹出: list.pop()
• 从一开始就弹出: list.pop(0)
• 扩展名单: list.append(x)

额外的功劳,拼接或任意流行音乐.

让我们说我有一个数组:

int a [] = {4,5,7,10,2,3,6}

当我访问一个元素,如[3]时,它在场景后面实际发生了什么？为什么许多算法书籍(如Cormen书籍......)说它需要一个恒定的时间？

(我只是低级编程的菜鸟,所以我想向你们学习更多)