Материал подготовил: Виталий Евтушенко, НИУ ВШЭ
Многие понятия в компьютерной науке и программировании были придуманы и концептуализированы задолго до появления ЯП Python, а порой и до появления компьютеров в нашем понимании этого.
Одной из таких концепций, существующих в компьютерной науке является абстрктный тип данных (abstract data type), обитающий на более высоком уровне абстракции, чем обычный тип данных (есть обычный, а есть абстрктный, он более абстрактный, чем обычный) и структура данных (как данные хранятся, какие методы поддерживаются, какова сложность методов из-за особенностей хранения данных).
В общем виде, можно сказать, что абстрактный тип данных является нашим идеальным представлением о том, как должно быть (какие функции реализованы, как себя ведет), а с помощью структуры данных мы реализуем (implementation) это идеальное представление на ЭВМ.
В общем виде, цикл в программировании - это управляющая конструкция
Каждая вычислительная операция, например, сложение двух простых чисел или же вычисление матрицы попырных расстояний, имеет свою вычислительную сложность, которая определяет. Сложность и по времени, и по памяти можно измерить (например, запустить алгоритм много раз и замерить время, или затраты памяти) или описать функцией.
Выделяют сложность в лучшем, в среднем и в худшем случаях (некоторые алгоритмы очень зависят от данных и их структур, которые подаются на вход).
$O$ - нотация - асимптотическое ограничение функции, описывающей алгоритм, сверху (не более). Отражает изменение времени выполнения в зависимости от изменения числа элементов.
фраза «сложность алгоритма есть O(f(n))» означает, что с увеличением параметра n, характеризующего количество входной информации алгоритма, время работы алгоритма будет возрастать не быстрее, чем некоторая константа, умноженная на f(n);
$\Omega$ - нотация - как и $O$- нотация - это асимптотическое ограничение функции, описывающей алгоритм, но уже снизу (не менее). В реальной жизни много чаще используется O - нотация.
Стоит повторно ометить, что сложность алгоритма обычно принято описывать по члену с максимальной степени (при стремлении к бесконечности, степень возрастает быстрее, чем коэфициент). Например, если в $O$-нотации алгоритм работает за $O(n^3 + 8n + \sqrt{9n})$ (какой-нибудь поиск на графе, в том числе социальном), то его запишут, как $O(n^3)$.
Почему важно?
Полезные ссылки:
Сортировка (англ. sorting) - упорядочивание, последовательное расположение объектов в зависимости от выбранного критерия (определяем этим критерием последовательность расположения, правило упорядочивания). Примеры: отсортировать по возрастанию, отсортировать так, чтобы на чётных местах объекты были расположены согласно убиванию их квадратных корней, а на нечётных согласно возрастанию их кубических значений.
Формулировка задачи сортировки
На что обратить внимание?
Полезные ссылки:
](https://www.youtube.com/watch?v=XaqR3G_NVoo) - ансамбли, танцующие под классическую и народную музыку, своими движениями и перестановками визуализирующие алгоритмы. (сюда стоит зайти)
Замерить время исполнения алгоритма в Jupiter'e можно, используя одну из следующих магических команд (рассмотрены на первом занятии) или с помощью модуля datetime
def big_loop():
i = 0
while i < 10000000:
i += 1
# измеряет время
%time {big_loop()}
CPU times: user 4 µs, sys: 0 ns, total: 4 µs Wall time: 7.87 µs
%%timeit
# запускает ячейку n раз, замеряя среднее время выполнения и выводя его в приятном виде
big_loop()
661 ms ± 113 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
#с помощью модуля datetime
class timeit():
from datetime import datetime
def __enter__(self):
self.tic = self.datetime.now()
def __exit__(self, *args, **kwargs):
print('runtime: {}'.format(self.datetime.now() - self.tic))
with timeit():
# your code, e.g.,
big_loop()
runtime: 0:00:00.515888