开始研究复杂性,我正在努力解决这个问题:
void what(int n) {
int i;
for (i = 1; i <= n; i++) {
int x = n;
while (x > 0)
x -= i;
}
}
好吧,第一个循环显然是O(n).第一次迭代是O(n),第二次是O(n/2)..而且就像log(n)我猜的那样？这意味着O(n) * O(log(n)) = O(n * log(n)) complexity.我做对了吗？
编辑:(不是重复)我知道Big O是什么.我已经在特定情况下询问了正确的评估.
来自维基百科:
算法的复杂性是
O(n(logn)(loglogn))位操作.
你怎么到达那个？
复杂性包括这个loglogn术语告诉我有一个sqrt(n)地方.
假设我在前100个数字(n = 100)上运行筛子,假设将数字标记为复合需要恒定时间(数组实现),我们使用的次数mark_composite()将类似于
n/2 + n/3 + n/5 + n/7 + ... + n/97 = O(n^2)
并且为了找到下一个素数(例如,7在越过所有数字的多个之后跳转到5),操作的数量将是O(n).
因此,复杂性将是O(n^3).你同意吗？
我正在考虑用软件排序算法,以及可以克服O(nlogn)障碍的可能方法.我不认为在实际意义上可以更快地排序,所以请不要认为我这样做.
话虽如此,似乎几乎所有的排序算法,软件必须知道每个元素的位置.这是有道理的,否则,它如何知道根据某些排序标准放置每个元素的位置？
但是,当我将这个想法与现实世界交叉时,离心机不知道每个分子在按密度分类时的位置.事实上,它并不关心每个分子的位置.然而,由于每个分子都遵循密度和引力定律 - 这让我思考,因此它可以在相对较短的时间内将数万亿个项目分类万亿.
是否有可能在每个节点上有一些开销(某些值或方法加到每个节点上)以"强制"列表的顺序？像离心机这样的东西,只有每个元素都关心它在空间中的相对位置(与其他节点相关).或者,这是否违反了计算中的某些规则？
我认为这里提出的一个重点是自然的量子力学效应以及它们如何同时平行应用于所有粒子.
也许经典计算机固有地限制了对域的排序O(nlogn),其中量子计算机可能能够跨越该阈值并入O(logn)并行的算法.
离心机基本上是平行气泡排序似乎是正确的,其时间复杂度为O(n).
我想下一个想法是,如果大自然可以排序O(n),为什么不能计算机？
我无法确定Euclid最大公分母算法的时间复杂度.这个伪代码算法是:
function gcd(a, b)
while b ? 0
t := b
b := a mod b
a := t
return a
它似乎取决于a和b.我的想法是时间复杂度是O(a%b).那是对的吗？有没有更好的方法来写这个？
我试图列出常见数据结构的操作的时间复杂性,如数组,二进制搜索树,堆,链表等,尤其是我指的是Java.它们很常见,但我想我们中的一些人对确切的答案并不是100%有信心.任何帮助,特别是参考,非常感谢.
例如,对于单链表:更改内部元素是O(1).你怎么能这样做？你HAVE更改它之前要搜索的元素.另外,对于Vector,添加内部元素为O(n).但是为什么我们不能在使用索引的摊销常数时间内做到这一点？如果我错过了什么,请纠正我.
我发布我的发现/猜测作为第一个答案.
String#substring()Java中方法的时间复杂度是多少？
是否有任何算法来计算子线性时间内的第n个斐波纳契数？
在CLRS,第三版,第155页,给出了在MAX-HEAPIFY中,
孩子们的子树每个都有2n/3的大小- 最坏的情况发生在树的底层正好是半满的时候.
我理解为什么当树的底层正好是半满时它是最糟糕的.并且在这个问题中也回答了MAX-HEAPIFY中的最坏情况:"最坏的情况发生在树的底层恰好是半满的时候"
我的问题是如何获得2n/3？
为什么如果底层是半满的,那么子树的大小是2n/3？
怎么计算？
谢谢
我正在寻找stackoverflow Non-Trivial Lazy Evaluation,这让我想到了Keegan McAllister的演讲:为什么要学习Haskell.在幻灯片8中,他显示了最小功能,定义为:
minimum = head . sort
并指出其复杂性为O(n).我不明白为什么如果通过替换排序是O(nlog n),复杂性被认为是线性的.帖子中引用的排序不能是线性的,因为它不假设数据的任何内容,因为线性排序方法需要它,例如计数排序.
懒惰的评价在这里发挥着神秘的作用吗？如果是这样,背后的解释是什么？
我们都知道在Python中执行语句一定次数的常用方法是使用for循环.
这样做的一般方法是,
# I am assuming iterated list is redundant.
# Just the number of execution matters.
for _ in range(count):
pass
我相信没有人会争辩说上面的代码是常见的实现,但是还有另一种选择.通过乘以引用来使用Python列表创建的速度.
# Uncommon way.
for _ in [0] * count:
pass
还有旧的while方式.
i = 0
while i < count:
i += 1
我测试了这些方法的执行时间.这是代码.
import timeit
repeat = 10
total = 10
setup = """
count = 100000
"""
test1 = """
for _ in range(count):
pass
"""
test2 = """
for _ in [0] …