http://github.com/heineman/LearningAlgorithms.
3 Ұнайды
программах используются три свободно распространяемые библиотеки Python, которые необходимо скачать и установить самостоятельно2:
• NumPy (https://www.numpy.org) версии 1.19.5;
• SciPy (https://www.scipy.org) версии 1.6.0;
• NetworkX (https://networkx.org) версии 2.5.
NumPy и SciPy — одни из самых популярных свободных библиотек с огромным сообществом. Я их использую, чтобы измерить фактическую производительность алгоритмов. NetworkX — большой сборник эффективных алгоритмов для работы с графами,
2 Ұнайды
Встроенные же функции, например max(), — часть самого интерпретатора: пока такая функция обрабатывает объект, не нужно ничего дополнительно интерпретировать. Поэтому встроенные функции всегда быстрее тех, что написаны на Python8. Следует заметить, что во всех случаях реализация одного и того же алгоритма должна приводить к одинаковому изменению быстродействия при изменении размера данных — например, при удвоении N время работы и largest(), и max() тоже удваивается как в наихудшем, так и в наилучшем случае.
1 Ұнайды
В книге будут появляться таблицы с подсчетом количества выполненных действий и затраченного времени наподобие табл. 1.2, где измерялось количество сравнений >. Строки таких таблиц соответствуют различным объемам входных данных. Если просмотреть таблицу сверху вниз, становится понятно, как растут показания в каждом столбце по мере удвоения размера данных.
Подсчет количества сравнений показывает, как работают функции largest() и alternate(). При удвоении N количество сравнений в largest() удваивается, а в alternate() — увеличивается вчетверо. Это поведение вполне стабильно, и несложно предсказать, как оба алгоритма поведут себя на данных большего размера. На рис. 1.5 показано, что количество сравнений в функции alternate() (отмечено по оси Y с левой стороны) довольно точно соответствует ее производительности (затраченное время отмечено по оси Y с правой стороны).
Начальный элемент массива A длиной N имеет индекс 0 и обозначается A[0], конечный обозначается A[N-1] и имеет индекс N – 1.
Зная номер i элемента в массиве, можно прочитать оттуда элемент Ae[i] или записать на место A[i] новое значение. При этом i — это индекс в диапазоне от 0 до N – 1.
Длина массива всегда известна. В Python и Java ее можно задать в процессе работы программы, а в С — только заранее.
Чтобы изменить длину массива, необходимо выделить память под новый массив нужной длины и скопировать туда все данные из старого. Просто так размер массива уменьшить или увеличить нельзя.
Массив — фиксированный набор однотипных значений, занимающий один непрерывный фрагмент оперативной памяти. Это одна из самых старых и самых надежных структур данных. Если значений больше одного — программисты хранят их в массиве. На схеме изображен целочисленный массив из восьми элементов
Алгоритм — это пошаговая инструкция решения некоторой задачи, реализованная в виде программы. Программа должна возвращать правильный ответ за предсказуемое время. Изучая алгоритм, мы проверяем и правильность ответа (в том числе на всех допустимых входных данных), и его вычислительную сложность (возможно, есть более эффективные решения задачи).
Современные языки программирования бывают как компилируемые (С или C++), в которых текст программы перед запуском транслируется в машинные инструкции, так и интерпретируемые (Python или Java). Программа на интерпретируемом языке транслируется в промежуточное представление, называемое байт-кодом. Затем программа-интерпретатор, Python например (в свою очередь сам написанный на С и откомпилированный), разбирает и выполняет этот байт-код6. При этом некоторые функции, например min() и max(), встроены в Python — они написаны на С, скомпилированы в машинные инструкции и так выполняются.
Предположим, выполнение одной машинной инструкции центральным процессором некоторого компьютера требует фиксированного времени t. Тогда время T, затраченное на работу алгоритма на этом компьютере, можно выразить как T(N) = t × C(N).
• лучший случай — набор данных размером N, на котором алгоритм совершает наименьшее количество действий;
• худший случай — набор данных размером N, требующий наибольшего количества действий.