相关疑难解决方法(0)

我更喜欢尽可能少的正式定义和简单的数学.

大多数拥有CS学位的人肯定会知道Big O代表什么.它可以帮助我们衡量算法的实际效率(如何),如果你知道你试图解决的问题属于哪个类别,你可以弄清楚是否仍然可以挤出那么少的额外性能.¹

但我很好奇,你如何计算或近似算法的复杂性？

¹ _{但正如他们所说,不要过度,过早优化是所有邪恶的根源,没有正当理由的优化也应该得到这个名称.}

我问的更多关于这对我的代码意味着什么.我在数学上理解这些概念,我只是很难在概念上围绕它们的意思.例如,如果要对数据结构执行O(1)操作,我理解它必须执行的操作量不会增加,因为有更多项.而O(n)操作意味着您将对每个元素执行一组操作.有人可以在这里填空吗？

• 就像O(n ^ 2)操作究竟会做什么一样？
• 如果一个操作是O(n log(n)),这意味着什么呢？
• 有人必须抽烟才能写出O(x!)？

我已经看到这个术语"O(1)访问时间"曾经意味着"快速",但我不明白这意味着什么.我在同一个上下文中看到的另一个术语是"O(n)访问时间".有人可以用简单的方式解释这些术语的含义吗？

也可以看看

• 什么是大O符号？你用它吗？
• 8岁儿童的大O？

可能重复:
什么是Big O表示法？你用它吗？

大家好,

相当基本的可扩展性符号问题.

我最近收到了一篇关于我的python有序列表实现的帖子的评论"但要注意你的'有序集'实现是插入的O(N)"

很高兴知道,但我不确定这意味着什么.

我看过n(o)o(N),N(o-1)或N(o*o)等符号

上述符号是指什么？

我正在学习计算复杂性的课程,到目前为止,它给人的印象是它对开发人员没什么帮助.

我可能错了,但如果你以前走过这条道路,你能否提供一个例子,说明复杂性理论如何帮助你完成工作？非常感谢.

我有一个看起来像这样的循环

def slow_loop(array)
 array.each_with_index do |item, i|
   next_item = array[i+1]
   if next_item && item.attribute == next_item.attribute
     do_something_with(next_item)
   end
 end
end

除了改变do_something_with被调用的方式,我怎样才能使这个表现更好？

谢谢,

-C

PS

由于看起来这是一个'O(n)'操作,显然没有在这里获得性能,所以我选择的答案是使用已经封装了这个操作的ruby方法.感谢大家的帮助