分析递归算法
我经常被递归算法所困扰，这些算法似乎需要神奇的逻辑跳跃（由于墨水短缺而产生大量缩小的符号）。
我意识到另一种方法是简单地记住所有常见算法的 Big O 表示法，但在某个时刻，这种方法会失败。例如，我很乐意透露冒泡排序、插入排序、二叉树插入/删除、归并排序和快速排序的性能，但不要要求我直接提出 AVL 树或 Djikstra 的最短路径算法的性能我的头。
我在哪里可以得到：
- 递归算法分析的讨论，使用单词而不是大量的符号
- 练习问题以确认我新获得的理解实际上是正确的
示例：
坏：
Sigma ve T (1+cv)
可能的“好” ' 等价：
树中 1 个节点所需的工作量（即 1 + 节点的子节点数），然后对树中的每个元素执行一次，其中原始节点是根。
旁注：
我可以简单地观看每个算法的视频，因为没有办法让一个人的声音变成下标（或任何其他扭曲），但我怀疑与阅读文本描述相比，这会花费大量时间。
更新：
这是已解决问题的 1 个来源：http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-introduction-to-algorithms-sma-5503-fall-2005 / （这解决了上面的#2）
I've often been slightly stumped by recursive algorithms that seem to require magical leaps (with a large dose of shrunken notation born of an ink shortage) of logic.
I realize that the alternative is to simply memorize the Big O notation for all the common algorithms but at a certain point, that approach fails. For example, I am happy to disclose the performance for bubble sort, insertion sort, binary tree insertion/removal, mergesort, and quicksort but don't ask me to come up with the performance of AVL trees or Djikstra's shortest path algorithm off the top of my head.
Where can I go to get:
- A discussion of recursive algorithm analysis that uses words instead of a profusion of symbols
- Practice problems to confirm that my newly-obtained understanding is actually correct
Example:
Bad:
Sigma v e T (1+cv)
Possible 'good' equivalent:
The amount of work required for 1 node in the tree (which is 1+the # of children of a node), which is then executed once for every element in the tree where the original node is the root.
Side commentary:
I could simply watch a video for every single algorithm because there's no way to make one's voice turn into a subscript (or any of the other contortions) but I suspect that would take an inordinate amount of time compared to reading textual descriptions.
Update:
Here's 1 source of solved problems: http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-introduction-to-algorithms-sma-5503-fall-2005/ (this tackles #2 above)
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
TopCoders 拥有大量教程和详尽的解释。你尝试过吗？
http://www.topcoder.com/tc?d1=tutorials& ;d2=alg_index&module=静态
TopCoders has a great source of tutorials and thorough explanations. Have you tried them out?
http://www.topcoder.com/tc?d1=tutorials&d2=alg_index&module=Static
要“正式”回答这个问题...
示例问题来源：http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-introduction-to-algorithms-sma -5503-fall-2005/
CS 分析说明：http://en.wikipedia .org/wiki/Concrete_Mathematics。
To 'officially' answer this question...
Source of sample problems: http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-introduction-to-algorithms-sma-5503-fall-2005/
An explanation of analysis for CS: http://en.wikipedia.org/wiki/Concrete_Mathematics.