Сложность алгоритмов - упражнения

Question

Я готовлюсь к экзамену по вводному курсу по информатике, и у меня возникла проблема с темой сложности, как в «обычных» алгоритмах, так и в рекурсивных алгоритмах (обычно мы получаем эти вопросы в виде кода на C ).
Мне было интересно, есть ли где-нибудь в Интернете примеры в Интернете и / или книгах, которые охватывают эту тему на базовом уровне (не слишком базовом).
уровень вопросов, по крайней мере, такой:

образец упражнения альтернативный текст http://img42.imageshack.us/img42/4456/ex1j.jpg

Answer 1

Я нашел очень хорошее объяснение в Введение в алгоритмы .... но вам нужны некоторые математические знания, чтобы понять это.

Лекция (видео) для курса "Введение в алгоритмы" из Массачусетского технологического института в отношении асимптотической записи здесь .

Answer 2

Я также рекомендовал бы следовать этим видео-лекциям от MIT, доступным по адресу: http://academicearth.org/courses/introduction-to-algorithms.

Удачи!

Answer 3

Введение в алгоритмы Кормена, Лизерсона и Ривеста - лучшее общее введение в алгоритмы, которые я знаю.

Разработка и анализ компьютерных алгоритмов Ахо, Хопкрофтом и Уллманом также хороши. Но сложнее усвоить в качестве вводного текста, чем Введение в алгоритмы ...

И я люблю Программирование Жемчуга Джоном Бентли. Каждый должен прочитать это.

Answer 4

Формальным способом решения вашего упражнения будет:

Для проверки выполните следующую программу на языке 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;
}

Answer 5

Мой первый совет - не переходите к новым темам, пока не получите Часть сложности. Что касается текста для справки, Введение в алгоритм по Кормену является хорошим вариантом. Видите, в основном есть три способа выразить сложность Биг-о, омега и тэта нотации. Расчет сложности для итерационных алгоритмов довольно прост. Пройдите любую книгу и попрактикуйтесь в нескольких примерах. Для рекурсивного алгоритма прочитайте Теорема Мастера . Используя эту теорему, вы можете легко вычислить сложность для большинства рекурсивных вопросов. Ищите теорему мастеров в сети, и вы найдете несколько хороших учебников. Вы можете начать отсюда http://en.wikipedia.org/wiki/Master_theorem.