Курс 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"
- Управление экспортом элементов
- Метод __ilshift__ для битового сдвига влево
- Импорт с альтернативным именем
- Форматирование строк с f-строками
- Цикл for в Python
- Python: отсутствие точек с запятыми
- Создание Radio кнопок в tkinter
- Создание OrderedDict
- Оператор распаковки в Python
- Методы работы со списками
- Howdoi — получение ответов из терминала
- Непрерывная проверка в Python
- Оператор is в Python
- Автоматизация с Python
- Библиотека Chartify: руководство
- Определение индекса элемента списка
- Округление дробей в Python
- Группы исключений в Python
- Библиотека sh: использование команд bash в Python
- Именованные кортежи в Python
- Объединение словарей в Python
- Метод difference_update() — разность множеств
- Установка и использование emoji
- Установка и использование модуля «howdoi»
- Работа со словарями Python
- Установка random seed в Python
- Namedtuple в Python
- Принцип одной функции
- Хеши в Python
- Переопределение метода delitem в Python
- Получение имени функции с помощью inspect
- Нарезка списков в Python
- Запрос DELETE с библиотекой requests
- Отделение звука от видео
- Разделение строки с регулярными выражениями
- GitHub в Telegram: подписка на уведомления
- Метод classmethod
- Списки в Python: основы
- Методы и функции в Python
- Удаление и повторная вставка ключа в OrderedDict
- Извлечение аудио из видео
- Проверка элементов списка условием
- Структуры данных в Python
- Лямбда-функции в defaultdict
- Измерение времени выполнения кода
- Декоратор проверки активности
- Инверсия списка и строки















