Is there any good resource (book, reference, web site, application...) which explains how to compute time complexity of an algorithm?
是否有任何好的资源(书籍,参考,网站,应用......)解释了如何计算算法的时间复杂度?
Because, it is hard to make the things concrete in my mind. Sometimes it is talking about an iteration has time complexity of lg n; and then according to the another loop it becomes n.lg n; and sometimes they use big omega notation to express it, sometimes big-o and etc...
因为,在我的脑海里很难让事情具体化。有时它正在谈论迭代的时间复杂度为lg n;然后根据另一个循环它变成n.lg n;有时候他们会使用大的欧米茄表示法来表达它,有时候会用big-o等...
These things are quite abstract to me. So, I need a resource which has good explanation and a lot of examples to make me see what's goin on.
这些东西对我来说都很抽象。因此,我需要一个具有良好解释和大量示例的资源,以便让我了解其中的内容。
Hopefully, I explained my problem clearly. I am quite sure that everyone who just started to study algorithms has also the same problem with me. So, maybe those experienced guys can also share their experience with us. Thanks...
希望我清楚地解释了我的问题。我很确定刚刚开始研究算法的每个人也遇到了同样的问题。所以,也许那些有经验的人也可以与我们分享他们的经验。谢谢...
7 个解决方案
#1
10
I think the best book is Introduction to Algorithms by Cormen, Leiserson, Rivest and Stein.
我认为最好的书是Cormen,Leiserson,Rivest和Stein的算法导论。
Here is it on Amazon.
这是在亚马逊上。
#2
5
Guys, you're all recommending true complexity theory books -- Arora and Barak contains all sorts of things like PCP, Interactive Proofs, Quantum Computing and topics on Expander graphs -- things that most programmers/software developers have never heard of or will ever use. Papdimitriou is in the same category. Knuth is freaking impossible to read (and I was a CS/Math major) and gives zero intuition on how things work.
伙计们,你们都推荐真正的复杂性理论书籍--Arora和Barak包含各种各样的东西,如PCP,交互式证明,量子计算和扩展器图形主题 - 大多数程序员/软件开发人员从未听说过或将来都会遇到的事情使用。 Papdimitriou属于同一类别。 Knuth很难读懂(而且我是CS / Math专业)并对事物的运作方式没有直觉。
If you want a simple way to compute runtimes, and to get the flavour of the analysis, try the first chapter or so of Kleinberg and Tardos "Design and Analysis of Algorithms", that holds your hand through the fundamentals, and then you can work on much harder problems.
如果您想要一种简单的方法来计算运行时间并获得分析的味道,请尝试Kleinberg和Tardos的第一章左右“算法的设计和分析”,它掌握了基础知识,然后您就可以工作了在更难的问题上。
#3
2
I read Christos Papadimitriou's Computational Complexity in university and really enjoyed it. It's not an easy matter, the book is long but it's well written (i.e., understandable and suitable for self-teaching) and it contains lots of useful knowledge, much more than just the "how do I figure out time complexity of algorithm x".
我在大学读过Christos Papadimitriou的计算复杂性并且非常喜欢它。这不是一件容易的事,这本书很长,但写得很好(即可以理解,适合自学),它包含了许多有用的知识,而不仅仅是“如何计算算法x的时间复杂度” 。
#4
2
I agree that Introduction to Algorithms is a good book. For more detailed instructions on e.g. how to solve recurrence relations see Knuth's Concrete Mathematics. A good book on Computational Complexity itself is the one by Papadimitriou. But that last book might be a bit too thorough if you only want to calculate the complexity of given algorithms.
我同意算法入门是一本好书。有关例如更详细的说明如何解决递归关系请参见Knuth的具体数学。关于计算复杂性本书的好书是Papadimitriou的书。但是,如果您只想计算给定算法的复杂性,那么最后一本书可能会有点过于彻底。
A short overview about big-O/-Omega notation:
关于big-O / -Omega表示法的简短概述:
- If you can give an algorithm that solves a problem in time T(c*(n log n)) (c being a constant), than the time complexity of that problem is O(n log n). The big-O gets rid of the c, that is any constant factors not depending on the input size n. Big-O gives an upper bound on the running time, because you have shown (by giving an algorithm) that you can solve the problem in that amount of time.
- If you can give a proof that any algorithm solving the problem takes at least time T(c*(n log n)) than the problem is in Omega(n log n). Big-Omega gives a lower bound on the problem. In most cases lower bounds are much harder to proof than upper bounds, because you have to show that any possible algorithm for the problem takes at least T(c*(n log n). Knowing a lower bound does not mean knowing an algorithm that reaches that lower bound.
- If you have a lower bound, e.g. Omega(n log n), and an algorithm that solves the problem in that time (an upper bound), than the problem is in Theta(n log n). This means an "optimal" algorithm for this problem is known. Of course this notation hides the constant factor c which can be quite big (that's why I wrote optimal in quotes).
如果你能给出一个解决时间问题T(c *(n log n))(c是一个常数)的算法,那么该问题的时间复杂度就是O(n log n)。 big-O摆脱了c,即任何不依赖于输入大小n的常数因子。 Big-O给出了运行时间的上限,因为您已经(通过给出算法)显示您可以在这段时间内解决问题。
如果你可以证明解决问题的任何算法至少花费时间T(c *(n log n))而不是Omega(n log n)中的问题。 Big-Omega给出了问题的下限。在大多数情况下,下限比上限更难以证明,因为你必须证明任何可能的问题算法至少需要T(c *(n log n)。知道下限并不意味着知道一个算法达到那个下限。
如果你有一个下限,例如Omega(n log n)和一个解决该时间问题的算法(上限),而不是问题在Theta(n log n)中。这意味着已知该问题的“最佳”算法。当然,这种符号隐藏了常数因子c,它可能非常大(这就是我在引号中写出最佳值的原因)。
Note that when using these notations you are usually talking about the worst-case running time of an algorithm.
请注意,使用这些表示法时,您通常会讨论算法的最坏情况运行时间。
#5
1
Computational complexity theory article in Wikipedia has a list of references, including a link to the book draft Computational Complexity: A Modern Approach, a textbook by Sanjeev Arora and Boaz Barak, Cambridge University Press.
*中的计算复杂性理论文章有一系列参考文献,包括“计算复杂性:现代方法”一书的摘要,以及剑桥大学出版社的Sanjeev Arora和Boaz Barak的教科书。
#6
0
The classic set of books on the subject is Knuth's Art of Computer Programming series. They're heavy on theory and formal proofs, so brush up on your calculus before you tackle them.
关于这一主题的经典书籍是Knuth的计算机编程艺术系列。他们在理论和形式证据上都很重要,所以在解决之前要先研究一下你的微积分。
#7
0
A course in Discrete Mathematics is sometimes given before Introduction to Algorithms.
在算法导论之前,有时会给出离散数学课程。
#1
10
I think the best book is Introduction to Algorithms by Cormen, Leiserson, Rivest and Stein.
我认为最好的书是Cormen,Leiserson,Rivest和Stein的算法导论。
Here is it on Amazon.
这是在亚马逊上。
#2
5
Guys, you're all recommending true complexity theory books -- Arora and Barak contains all sorts of things like PCP, Interactive Proofs, Quantum Computing and topics on Expander graphs -- things that most programmers/software developers have never heard of or will ever use. Papdimitriou is in the same category. Knuth is freaking impossible to read (and I was a CS/Math major) and gives zero intuition on how things work.
伙计们,你们都推荐真正的复杂性理论书籍--Arora和Barak包含各种各样的东西,如PCP,交互式证明,量子计算和扩展器图形主题 - 大多数程序员/软件开发人员从未听说过或将来都会遇到的事情使用。 Papdimitriou属于同一类别。 Knuth很难读懂(而且我是CS / Math专业)并对事物的运作方式没有直觉。
If you want a simple way to compute runtimes, and to get the flavour of the analysis, try the first chapter or so of Kleinberg and Tardos "Design and Analysis of Algorithms", that holds your hand through the fundamentals, and then you can work on much harder problems.
如果您想要一种简单的方法来计算运行时间并获得分析的味道,请尝试Kleinberg和Tardos的第一章左右“算法的设计和分析”,它掌握了基础知识,然后您就可以工作了在更难的问题上。
#3
2
I read Christos Papadimitriou's Computational Complexity in university and really enjoyed it. It's not an easy matter, the book is long but it's well written (i.e., understandable and suitable for self-teaching) and it contains lots of useful knowledge, much more than just the "how do I figure out time complexity of algorithm x".
我在大学读过Christos Papadimitriou的计算复杂性并且非常喜欢它。这不是一件容易的事,这本书很长,但写得很好(即可以理解,适合自学),它包含了许多有用的知识,而不仅仅是“如何计算算法x的时间复杂度” 。
#4
2
I agree that Introduction to Algorithms is a good book. For more detailed instructions on e.g. how to solve recurrence relations see Knuth's Concrete Mathematics. A good book on Computational Complexity itself is the one by Papadimitriou. But that last book might be a bit too thorough if you only want to calculate the complexity of given algorithms.
我同意算法入门是一本好书。有关例如更详细的说明如何解决递归关系请参见Knuth的具体数学。关于计算复杂性本书的好书是Papadimitriou的书。但是,如果您只想计算给定算法的复杂性,那么最后一本书可能会有点过于彻底。
A short overview about big-O/-Omega notation:
关于big-O / -Omega表示法的简短概述:
- If you can give an algorithm that solves a problem in time T(c*(n log n)) (c being a constant), than the time complexity of that problem is O(n log n). The big-O gets rid of the c, that is any constant factors not depending on the input size n. Big-O gives an upper bound on the running time, because you have shown (by giving an algorithm) that you can solve the problem in that amount of time.
- If you can give a proof that any algorithm solving the problem takes at least time T(c*(n log n)) than the problem is in Omega(n log n). Big-Omega gives a lower bound on the problem. In most cases lower bounds are much harder to proof than upper bounds, because you have to show that any possible algorithm for the problem takes at least T(c*(n log n). Knowing a lower bound does not mean knowing an algorithm that reaches that lower bound.
- If you have a lower bound, e.g. Omega(n log n), and an algorithm that solves the problem in that time (an upper bound), than the problem is in Theta(n log n). This means an "optimal" algorithm for this problem is known. Of course this notation hides the constant factor c which can be quite big (that's why I wrote optimal in quotes).
如果你能给出一个解决时间问题T(c *(n log n))(c是一个常数)的算法,那么该问题的时间复杂度就是O(n log n)。 big-O摆脱了c,即任何不依赖于输入大小n的常数因子。 Big-O给出了运行时间的上限,因为您已经(通过给出算法)显示您可以在这段时间内解决问题。
如果你可以证明解决问题的任何算法至少花费时间T(c *(n log n))而不是Omega(n log n)中的问题。 Big-Omega给出了问题的下限。在大多数情况下,下限比上限更难以证明,因为你必须证明任何可能的问题算法至少需要T(c *(n log n)。知道下限并不意味着知道一个算法达到那个下限。
如果你有一个下限,例如Omega(n log n)和一个解决该时间问题的算法(上限),而不是问题在Theta(n log n)中。这意味着已知该问题的“最佳”算法。当然,这种符号隐藏了常数因子c,它可能非常大(这就是我在引号中写出最佳值的原因)。
Note that when using these notations you are usually talking about the worst-case running time of an algorithm.
请注意,使用这些表示法时,您通常会讨论算法的最坏情况运行时间。
#5
1
Computational complexity theory article in Wikipedia has a list of references, including a link to the book draft Computational Complexity: A Modern Approach, a textbook by Sanjeev Arora and Boaz Barak, Cambridge University Press.
*中的计算复杂性理论文章有一系列参考文献,包括“计算复杂性:现代方法”一书的摘要,以及剑桥大学出版社的Sanjeev Arora和Boaz Barak的教科书。
#6
0
The classic set of books on the subject is Knuth's Art of Computer Programming series. They're heavy on theory and formal proofs, so brush up on your calculus before you tackle them.
关于这一主题的经典书籍是Knuth的计算机编程艺术系列。他们在理论和形式证据上都很重要,所以在解决之前要先研究一下你的微积分。
#7
0
A course in Discrete Mathematics is sometimes given before Introduction to Algorithms.
在算法导论之前,有时会给出离散数学课程。