我在学习算法,需要你们帮助我。如果我的问题不明确,我是一个初学者,所以请原谅我。当我在学习的时候,我看到了像NlogN,N^2等类似的东西。帮助学习算法基础知识
当涉及到使用这些符号检查不同算法的效率/性能时,我并不十分清楚它的含义。我非常了解对数,但它们在检查算法性能方面的使用方式让我很生气。
我在问,如果有人能指点我一个教程,在这个教程里已经解释了这些符号,这样我就可以很好地理解基础知识。我真的很想了解他们,并且愿意学习。
感谢您的帮助。
Kap。
我在学习算法,需要你们帮助我。如果我的问题不明确,我是一个初学者,所以请原谅我。当我在学习的时候,我看到了像NlogN,N^2等类似的东西。帮助学习算法基础知识
当涉及到使用这些符号检查不同算法的效率/性能时,我并不十分清楚它的含义。我非常了解对数,但它们在检查算法性能方面的使用方式让我很生气。
我在问,如果有人能指点我一个教程,在这个教程里已经解释了这些符号,这样我就可以很好地理解基础知识。我真的很想了解他们,并且愿意学习。
感谢您的帮助。
Kap。
购买Introduction to Algorithms。您可以以实惠的价格获得二手版本。
和/或查看这些来自MIT的great online video lectures围绕上述书建立。
通过查看这些演讲,你就会明白一些算法是如何具有对数时间复杂度,而有些人指数等
+1您阅读了我的想法 – 2010-10-25 20:30:32
你所描述什么叫big O notation。 Here是解释它的指南。
重要的是要注意的是,符号忽略了无关紧要的术语。如果你的算法需要6X^2 + 3X + 12秒来执行,其中X是正在处理的数据点的数量,所以称它为O(X^2),因为当X变大时,6并没有真正的区别,也不会是3,也不是12。
由父母提供的美妙链接。记住排序算法:如何排序无序集?如果你做得不太聪明,你最终会得到O(n^2),并且有更复杂的算法,你可以在O(log n)中做到这一点。 – Roalt 2010-10-25 20:34:29
http://www.amazon.com/Structures-Algorithm-Analysis-Allen-Weiss/dp/0805390529是最好的书籍之一,将以优秀的方式解释算法。
--Cheers
你在谈论Big-O符号。这种符号是一种描述算法的最坏可能运行时间作为其输入大小的函数的方式。 (n^2)表示如果输入的大小为n(例如其中包含n个元素的列表),则该算法将需要n^2次通过以在最坏情况下执行情景(Big-O是最糟糕的情况;对于最好的情况和平均情况,还有其他符号)。如果您有一个for循环嵌套在另一个循环中,则可能会发生这种情况,并且两者都从1运行到n。
O(nlogn)是相似的。它通常发生在遍历树结构时(如二叉树)。
请注意,您可能永远不会看到像O(3n)这样的东西,因为对于非常大的n值,常量3并不重要,所以它将被简化为O(n)。
许多其他人已经发布了很好的链接阅读。
请参阅http://stackoverflow.com/questions/133008/what-is-big-o-notation-do-you-use-it – Roalt 2010-10-25 20:36:20