Курс 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"
- Применение функции map() в Python
- Работа с изображениями PIL
- Сравнение объектов в Python
- Работа с переменными в Python
- Работа со списками
- Расчет времени выполнения
- Генератор чисел Фибоначчи
- Создание словарей с defaultdict()
- Извлечение новостей с newspaper3k
- Импорт модулей в Python 3.12
- Объединение словарей в Python
- Метод join для наборов
- Слияние словарей в Python 3.9
- Методы работы со строками в Python
- Нарезка списков в Python
- Создание детектора плагиата
- Работа с Path в Python
- Отладчик pdb: начало работы
- Определение объема памяти объекта
- Объединение списков в строку
- Метод __int__ в Python
- Создание коллекций из генератора
- Оптимизация памяти с __slots__
- Метод join() для объединения элементов в строку.
- List Comprehension Tutorial
- Работа с SQLite в Python
- Удаление элемента из списка в Python
- Поиск самого длинного слова в списке с использованием max()
- lru_cache оптимизация функций
- Работа с часовыми поясами в Python
- split() — разделение строки
- Counter() — подсчет элементов
- Перевод двоичного кода в целое число
- Метод __complex__ в Python
- Модуль inspect
- Описание скриптов в README
- Функция zip() — объединение последовательностей
- Глобальные переменные в Python
- Работа с асинхронными задачами в Python
- Структура данных deque в Python
- Numpy: разбиение массивов
- Модуль xkcd: добавление юмора в Python
- Обход словаря в Python
