Стивен С. Скиена - Алгоритмы. Руководство по разработке

................................................................................................................................ .49
Замечания к главе .......................................................................................................................... 50
1.9. Упражнения ............................................................................................................................. 50
Поиск контрпримеров ............................................................................................................ 50
Доказательство правильности ............................................................................................... 51
Математическая индукция ..................................................................................................... 52
Приблизительные подсчеты .................................................................................................. 52
Проекты по реализации ......................................................................................................... 53
Задачи, предлагаемые на собеседовании ............................................................................. 53
LeetCode .................................................................................................................................. 54
HackerRank .............................................................................................................................. 54
Задачи по программированию .............................................................................................. 54

Оглавление

6
Глава

2.1.

2. Анализ

алгоритмов ....................................................................................... 55

Модель вычислений

RAM ..................... " ................. " ... " ............. " ... "" .............. " ........... " .. "55
2.1.1. Анализ сложности наилучшего, наихудшего и среднего случая """""""""""""".56
2.2. Асимптотические («Big Oh») обозначения ........................................................ "" ..... " ........ 58
ОСТАНОВКА ДЛЯ РАЗМЫШЛЕНИЙ: Возвращение к определениям """"""""""""""""""""""61
ОСТАНОВКА для РАЗМЫШЛЕНИЙ: Квадраты ...... " ................................................................ " .... 61
2.3. Скорость роста и отношения доминирования"""""""""""""""""""""""""""""""""""61
2.3.1. Отношения доминирования """""""".""".""."""""""".""""."""""""""""""""".63
2.4. Работа с асимптотическими обозначениями """"""".""."""""""""".""""""""""""""."64
2.4.1. Сложение функuий" ............................... " ....... " ........................................................... 64
2.4.2. Умножение функuий ............... " .......... " ........................... " .......................................... 64
ОСТАНОВКА для РАЗМЫШЛЕНИЙ: Транзитивность""""""""" .. """"".".""""""""."""""""" 65
2.5. Оuенка эффективности ............................. " ............... " ... "" ................... " ............................... 65
2.5.1. Сортировка методом выбора .... " ........................................... " ......... " ................ " ....... 65
Доказываем временную сложность 0-большое """"""""""""""""""" .. """"""""66
2.5.2. Сортировка вставками """ ..... " ... " ..... "" ........................... " ......................................... 67
Доказываем временную сложность 0-большое """"""""""""""""""""""""""""68
2.5.3. Сравнение строк " ... " ....... " ..................... " ................................... " .... " ......................... 68
Доказываем время исполнения по 0-большое """""""""""""""""""""""""""""69
......... " ..... " .................................................................... " .. "" .. " .... 70
2.6. Суммирование ....................................... " .......... " ........................ " .................._." ........ " ........... 71
ОСТАНОВКА ДЛЯ РАЗМЫШЛЕНИЙ: Формулы факториала """""""""""""""""""""""""""". 72

2.5.4.

Умножение матриu

2.7. Логарифмы и их применение""".""""""""""."""""""""""""""""."".""""""""."".""".73
2.7.1. Логарифмы и двоичный поиск".""""""""""."""""""""""""""""""""""""""."".73
2.7.2. Логарифмы и деревья """"""""""""""""""""""""""""."""""""""""""""""""".74
2.7.3. Логарифмы и --">