Курс Python → Big O оптимизация
Big O оптимизация — это важная задача для разработчиков. Оценка скорости работы программы на разных устройствах может быть сложной из-за различий в аппаратном обеспечении. Для универсальной оценки был разработан подход, использующий понятие Big O. Например, простой алгоритм перебора всех значений имеет сложность O(n), где n — количество значений, так как используется только один цикл. Если же есть два вложенных цикла, как в программе для вывода таблицы умножения, то сложность уже будет O(n^2). Из формул видно, что второй алгоритм работает намного медленнее.
Главное правило — чем больше данных, тем дольше будет работать программа. Например, бинарный поиск имеет сложность O(log n) и работает намного быстрее, но требует отсортированного списка. При оценке сложности учитывается количество проходов по данным, а не количество строк кода. График скорости работы алгоритмов показывает, что чем меньше операций выполняется, тем лучше.
Пример кода:
def linear_search(array, target):
for i in range(len(array)):
if array[i] == target:
return i
return -1
def binary_search(array, target):
low = 0
high = len(array) - 1
while low <= high:
mid = (low + high) // 2
if array[mid] == target:
return mid
elif array[mid] < target:
low = mid + 1
else:
high = mid - 1
return -1
В приведенных примерах кода показаны алгоритмы линейного и бинарного поиска. Линейный поиск имеет сложность O(n), так как выполняет n операций в худшем случае. Бинарный поиск имеет сложность O(log n) и работает быстрее, но требует отсортированного списка. Понимание Big O помогает разработчикам выбирать наиболее эффективные алгоритмы для своих задач.
Другие уроки курса "Python"
- Разделение строки на пары ключ-значение.
- Python: возвращение нескольких значений
- Переменные в Python: сокращение гласных
- Методы classmethod и staticmethod
- Numpy: использование Ellipsis
- Глобальные переменные в Python
- Установка и использование модуля «howdoi»
- Оператор is в Python
- Замена текста в Python
- Оператор (*) в Python
- Функциональное программирование.
- Удаление элемента по индексу
- Замена текста с re.sub()
- Проверка переменных окружения в Python
- Создание GUI на Tkinter
- Освобождение памяти в Python
- None в Python: использование и особенности
- Форматирование строк с % в Python
- Работа с комплексными числами
- Python defaultdict добавление ключа
- Абстракции словарей и множеств в Python
- Работа со слайсами
- Установка и использование Telegram API в Python
- Работа с коллекциями Python
- Работа со случайными элементами
- Упрощение условных выражений с тернарным оператором
- Замена символов в строке
- Декораторы в Python
- Преобразование многоуровневого словаря
- Применение функции map() в Python
- Работа с путями в Python
- Добавление элементов в список
- Python union() функция — объединение множеств
- Форматирование строк в Python.
- Преобразование данных в Python
- Проверка запуска скрипта или импорта модуля
- Проверка на палиндром
- Работа со строками
- Python: Фильтрация списков с помощью filter()
- Аннотации типов в Python
- Модуль subprocess: запуск внешних команд
- Модуль pprint
- Оператор морж в Python 3.8
- Эффективная конкатенация строк с использованием join()
- Использование super() в Python
- Метод get для словаря
