算法复杂度 - 练习

Question

我正在学习计算机科学入门课程的考试，并且在复杂性主题方面遇到了问题，无论是“常规”算法还是递归算法（通常我们会将这些问题编写为C代码）。 我想知道是否有互联网上的在线示例和/或书籍，以基本水平（不要太基础）涵盖该主题。至少问题的难度应像以下示例练习：

样本练习 alt text http://img42.imageshack.us/img42/4456/ex1j.jpg

- bks

---

除了Cormen的书，还有什么其他的内容吗？ - bks

http://www.cforcoding.com/2009/07/plain-english-explanation-of-big-o.html - Ionut Anghelcovici

在查看了这个和其他链接后，我明白了大O符号的含义。简而言之：对于足够大的n，2log(3.5n) + 2.4的行为与log(n)完全相同。我想我会去看MIT的讲座，但如果你有其他的东西，请在这里发布。 - bks

Answer 1

我在《算法导论》中找到了一个非常好的解释……但是你需要一些数学知识才能理解它。

麻省理工学院关于渐进符号的《算法导论》课程讲座（视频）在这里。

- Ionut Anghelcovici

---

你比我快了30秒。Cormen、Leiserson和Rivest所编写的《算法导论》是我所知道的最好的通用算法介绍。 - Tomek Szpakowicz

我实际上已经开始阅读它了，它涉及到我需要的内容，但是简要地提到了一下，然后详细阐述了其他事情。 我会看一下那个讲座，谢谢。 - bks

大O符号的介绍很简短。但是书中的每个算法都经过了彻底的分析。因此，整本书都充满了例子和练习。 - Tomek Szpakowicz

Answer 2

Cormen、Leiserson和Rivest的《算法导论》是我所知道的最好的通用算法介绍。

Aho、Hopcroft和Ullman的《计算机算法设计与分析》也不错。但相较于《算法导论》，作为入门教材更难以理解......

我喜欢Jon Bentley的《编程珠玑》。每个人都应该阅读它。

- Tomek Szpakowicz

Answer 3

我也建议您观看麻省理工学院的这些视频讲座，网址为：http://academicearth.org/courses/introduction-to-algorithms。

祝好运！

- Tomas Vinter

Answer 4

我给你的第一个建议是，在理解复杂性之前不要继续学习新主题。至于参考资料，《算法导论》（Cormen）是一个不错的选择。 基本上有三种方法来表达复杂度：大O符号、omega符号和theta符号。 对于迭代算法的复杂度计算非常简单。阅读任何一本书并练习一些例子即可。 对于递归算法，请阅读《Masters定理》。使用这个定理，你可以轻松地计算出大多数递归问题的复杂度。在网上搜索Masters定理，你会找到几个很好的教程。你可以从这里开始 http://en.wikipedia.org/wiki/Master_theorem。

- Duleb

---

Cormen的问题在于，我大多数时候只看到代码分析的最终结果，然后将其转换为O(n)符号，例如：T(n) = T(2n/3) + 1，我知道最终会得出O(n) = log(n)，但我需要更详细的说明如何从代码本身确定该公式（以及迭代算法公式）。也许我错了，这本书包含了我要找的内容，感谢您的回答！ - bks

这是一个递归算法的示例。我的建议是先了解递归的工作原理，然后再学习主定理。主定理有三种情况，几乎可以解决所有递归问题。 - Duleb

主定理涉及形式为：T(n) = aT(n/b) + f(n)的递归关系。这基本上意味着我们已将问题分解成子问题，每个子问题的大小为n/b。其中f(n)代表将子问题的解组合以获得最终完整解所需的工作量。 - Duleb

Answer 5

解决你的练习的正式方式是：

为了验证，请在C语言中执行以下程序（编译器为MinGW2.95）：

#include <stdio.h>
#include <math.h>
int main() {
    int sumIN = 0, sumOUT = 0;
    double i, n = 500, j;
    double d;
    for (i = 1; i <= n; i ++) {
        d = 1/(double)i;
        j = i;
        while (j > 0 && d > 0) {
            j -= d;
            sumIN ++;
        }
        sumOUT ++;
    }
    printf("\nsumIN = %d, sumOUT = %d", sumIN, sumOUT);
    printf("\n");
    return 0;
}

- Mohamed Ennahdi El Idrissi