Введение
Примеры
нотация
Основная идея
Нотация, используемая при описании скорости вашей программы на Python, называется нотацией Big-O. Допустим, у вас есть функция:
def list_check(to_check, the_list):
for item in the_list:
if to_check == item:
return True
return False
Это простая функция, чтобы проверить, есть ли элемент в списке. Чтобы описать сложность этой функции, вы скажете O (n). Это означает «порядок n», так как функция O называется функцией порядка.
O (n) - обычно n - количество предметов в контейнере
O (k) - обычно k - это значение параметра или количество элементов в параметре
Список операций
Операции: Средний регистр (предполагается, что параметры генерируются случайным образом)
Добавить: O (1)
Копировать: O (n)
Del slice: O (n)
Удалить элемент: O (n)
Вставить: O (n)
Получить предмет: O (1)
Установить предмет: O (1)
Итерация: O (n)
Получить срез: O (k)
Установить срез: O (n + k)
Расширить: O (k)
Сортировка: O (n log n)
Умножить: O (nk)
х в с: O (n)
мин (с), макс (с): O (n)
Получить длину: O (1)
Deque операции
Deque - это двусторонняя очередь.
class Deque:
def __init__(self):
self.items = []
def isEmpty(self):
return self.items == []
def addFront(self, item):
self.items.append(item)
def addRear(self, item):
self.items.insert(0,item)
def removeFront(self):
return self.items.pop()
def removeRear(self):
return self.items.pop(0)
def size(self):
return len(self.items)
Операции: Средний регистр (предполагается, что параметры генерируются случайным образом)
Добавить: O (1)
Дополнение: O (1)
Копировать: O (n)
Расширить: O (k)
Extendleft: O (k)
Pop: O (1)
Поплефт: O (1)
Удалить: O (n)
Повернуть: O (k)
Операции над множествами
Операция: Средний регистр (предполагается, что параметры генерируются случайным образом): Наихудший случай
х в с: O (1)
Разница s - t: O (len (s))
Пересечение s & t: O (мин (len (s), len (t))): O (len (s) * len (t)
Множественное пересечение s1 & s2 & s3 & ... & sn:: (n-1) * O (l), где l - это максимум (len (s1), ..., len (sn))
s.difference_update (t): O (len (t)): O (len (t) * len (s))
s.symetric_difference_update (t): O (len (t))
Симметричная разница s ^ t: O (len (s)): O (len (s) * len (t))
Union s | t: O (len (s) + len (t))
Алгоритмические обозначения ...
Существуют определенные принципы, применимые к оптимизации на любом языке программирования, и Python не является исключением. Не оптимизировать , как вы идете: Написать программу без учета возможных оптимизаций, сосредоточившись на том , что код чистый, правильный, и понятно. Если он слишком большой или слишком медленный, когда вы закончите, вы можете подумать об его оптимизации.
Помните правило 80/20: Во многих областях вы можете получить 80% результата с 20% усилий (также называемой 90/10 правило - это зависит от того, кто вы говорите). Всякий раз, когда вы собираетесь оптимизировать код, используйте профилирование, чтобы узнать, на что уходит 80% времени выполнения, чтобы вы знали, на чем сконцентрировать свои усилия.
Всегда запускать «до» и «после» тестов: Как еще вы будете знать , что ваши оптимизации фактически сделали разницу? Если ваш оптимизированный код оказывается только немного быстрее или меньше, чем оригинальная версия, отмените изменения и вернитесь к исходному, чистому коду.
Используйте правильные алгоритмы и структуры данных: не используйте алгоритм пузырьковой сортировки O (n2) для сортировки тысячи элементов при наличии быстрой сортировки O (n log n). Точно так же не храните тысячи элементов в массиве, который требует поиска O (n), когда вы можете использовать двоичное дерево O (log n) или хэш-таблицу Python O (1).
Для более перейдите по ссылке ниже ... Python Speed Up
Следующие 3 асимптотических обозначения в основном используются для представления временной сложности алгоритмов. 1) Θ Обозначения: Тета обозначение ограничивает функции сверху и снизу, так что он определяет точный асимптотическое поведение. Простой способ получить тэта-нотацию выражения - отбросить младшие члены и игнорировать ведущие константы. Например, рассмотрим следующее выражение. 3n3 + 6n2 + 6000 = Θ (n3) Отбрасывание членов более низкого порядка всегда хорошо, потому что всегда будет n0, после которого Θ (n3) имеет более высокие значения, чем Θn2), независимо от задействованных констант. Для данной функции g (n) обозначим Θ (g (n)) следующий набор функций. Θ (г (п)) = {F (п): существуют положительные константы c1, с2 и n0, что 0 <= с1 г (п) <= е (п) <= с2 г (п) для всех п> = n0} Данное определение означает, что если Р (п) тета д (п), то величина F (п) всегда находится между c1 г (п) и c2 г (п) при больших значениях п (п> = n0). Определение тета также требует, чтобы f (n) была неотрицательной для значений n, превышающих n0.
2) Big O нотация: Обозначение Big O определяет верхнюю границу алгоритма, он ограничивает функцию только сверху. Например, рассмотрим случай сортировки вставкой. Это занимает линейное время в лучшем случае и квадратичное время в худшем случае. Мы можем с уверенностью сказать, что временная сложность сортировки вставкой равна O (n ^ 2). Обратите внимание, что O (n ^ 2) также охватывает линейное время. Если мы используем обозначение to для представления временной сложности сортировки вставкой, мы должны использовать два оператора для лучшего и худшего случаев:
- Наихудшая временная сложность сортировки вставкой Θ (n ^ 2).
- Наилучшая временная сложность сортировки вставок Θ (n).
Обозначение Big O полезно, когда мы имеем только верхнюю границу временной сложности алгоритма. Много раз мы легко находим верхнюю границу, просто взглянув на алгоритм. O (g (n)) = {f (n): существуют положительные постоянные c и n0, такие что 0 <= f (n) <= cg (n) для всех n> = n0}
3) Ω Обозначения: Так же , как Big O обозначение дает асимптотическую верхнюю границу функции, Ω обозначение обеспечивает асимптотическую нижнюю границей. Ω Обозначение <может быть полезно, когда мы имеем нижнюю границу временной сложности алгоритма. Как обсуждалось в предыдущем посте, лучшая производительность алгоритма в общем случае бесполезна, нотация Omega - наименее используемая нотация из всех трех. Для данной функции g (n) обозначим через Ω (g (n)) множество функций. Ω (g (n)) = {f (n): существуют положительные постоянные c и n0, такие что 0 <= cg (n) <= f (n) для всех n> = n0}. Давайте рассмотрим тот же пример сортировки вставок здесь. Временная сложность сортировки вставкой может быть записана как Ω (n), но это не очень полезная информация о сортировке вставкой, так как нас обычно интересует наихудший случай, а иногда и средний случай.
