c - 算法的复杂性 - 练习

Question

我正在学习计算机科学入门课程的考试，并且在“常规”算法和递归算法（通常我们将这些问题编写为 C 代码）中，我都对复杂性主题有疑问。
我想知道互联网和/或书籍中是否有在线示例涵盖基本级别（不是太基本）的主题。
问题的级别至少像这样：

示例练习 alt text http://img42.imageshack.us/img42/4456/ex1j.jpg

Answer 1

我在Introduction to Algorithms中找到了一个很好的解释……但是你需要一些数学知识来理解它。

麻省理工学院算法介绍课程关于渐近符号的讲座（视频）在这里。

Answer 2

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

祝你好运！

Answer 3

Cormen、Leiserson 和 Rivest 的《算法简介》是我所知道的对算法的最佳一般简介。

Aho、Hopcroft 和 Ullman 的计算机算法设计和分析也不错。但作为介绍性文本比算法介绍更难消化......

我喜欢 Jon Bentley 的 Programming Pearls。每个人都应该阅读它。

Answer 4

我对您的第一个建议是，在您了解复杂性部分之前，不要进入新主题。至于要参考的文字，Cormen 的 Introduction to Algorithm是一个不错的选择。看到基本上有三种方式来表达复杂性 Big-oh、omega 和 theta 符号。迭代算法的复杂度计算非常简单。阅读任何一本书并练习一些例子。对于递归算法，请阅读Masters theorem。使用这个定理，您可以轻松计算大多数递归问题的复杂性。在网上搜索大师定理，你会发现几个很好的教程。你可以从这里开始http://en.wikipedia.org/wiki/Master_theorem。

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;
}