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

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

образец упражнения alt text http://img42.imageshack.us/img42/4456/ex1j.jpg Сложность алгоритмов - упражнений

источник

2009-09-01 bks

что-то кроме книги Кормена? – bks

http://www.cforcoding.com/2009/07/plain-english-explanation-of-big-o.html – 2009-09-01 08:18:53

, посмотрев на это и в других ссылках, я получил, я понимаю, что я знаю о большом O но вкратце: 2log (3.5n) + 2.4 ведет себя точно так же, как log (n) для n, достаточно большого. Я думаю, что посмотрю на лекции MIT, но если у вас есть что-то еще, пожалуйста, отправьте сообщение здесь – bks

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

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

источник

2009-09-01 07:29:56

Вы избили меня на 30 секунд. Введение в алгоритмы Cormen, Leiserson и Rivest - лучшее введение в общие алгоритмы, о которых я знаю. –

На самом деле я начал читать, он касается того, что мне нужно, но кратко, а затем уточняет другие вещи. Я возьму добычу на этой лекции, спасибо – bks

Введение в большую нотацию O короткое. Но тогда каждый алгоритм в книге тщательно анализируется. Итак, вся книга полна примеров и упражнений. –

Введение в алгоритмы Cormen, Leiserson и Rivest - лучшее общее введение в алгоритмы, о которых я знаю.

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

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

источник

2009-09-01 07:37:20

Я бы также рекомендовал следующие видео-лекции от Массачусетского технологического института, доступные по адресу: http://academicearth.org/courses/introduction-to-algorithms.

Удачи!

источник

2009-09-01 07:59:03

Благодарю вас, я взгляну на эту проблему – bks

Моим первым советом для вас было бы то, что не переходите к новым темам, пока не получите часть сложности . Что касается текста для консультации, Введение в алгоритм от Cormen - хороший вариант. См. В основном три способа выразить сложность Big-oh, omega и theta notation. Расчет сложности для итерационных алгоритмов довольно прост. Пройдите через любую книгу и приведите примеры. Для рекурсивного алгоритма читать Магистерская теорема. Используя эту теорему, вы можете легко вычислить сложность для большинства рекурсивных вопросов. Найдите теорему мастеров в сети, и вы найдете несколько хороших уроков. Вы можете начать здесь http://en.wikipedia.org/wiki/Master_theorem.

источник

2009-09-01 08:11:38 Duleb

, проблема с Cormen, например, в том, что я в основном вижу конечный результат анализа кода, который затем переводится в O (n) нотацию, suck as: T (n) = T (2n/3) + 1, о котором я знаю, что дает вам O (n) = log (n), но мне нужно больше уклонения в том, как определить формулу (и формулы итеративных алгоритмов) из самого кода. возможно, я ошибаюсь, и в книге есть то, что я ищу, спасибо за ваш ответ! – bks

Это в примере рекурсивного алгоритма. Я советую понять, что сначала понять, как работает рекурсия, а затем пройти через магистерскую теорему. Теорема Мастера имеет три случая, которые решают почти все рекурсивные задачи. – Duleb

Основная теорема касается рекуррентных соотношений вида: T (n) = aT (n/b) + f (n) Это в основном означает, что мы нарушили нашу проблему в подзадачи, и каждая подзадача имеет размер n /b. Здесь f (n) представляет собой усилие, необходимое для объединения решения подзадачи для получения окончательного полного решения. – Duleb

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

enter image description here

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

источник

2014-03-16 20:47:52

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

ответ

Смежные вопросы