Курс 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"
- Удаление дубликатов из списка с помощью dict.fromkeys
- Работа с итераторами через срезы
- Инвертирование словаря
- Метод lt для сортировки объектов
- PUT запрос для обновления данных
- JSON-esque в Python
- Структурирование именованных констант
- Функция enumerate в Python
- Python: библиотеки и функции
- Генерация случайных чисел в Python
- Поиск самого частого элемента
- kwargs в Python
- Удаление falsy-значений из списка с помощью filter
- Список переменных с %who
- Работа с Path в Python
- Выход из профиля в Django
- Сравнение def и lambda функций в Python
- Метод join() для объединения элементов
- Тест скорости набора текста на Python
- Удаление эмодзи с помощью pandas
- Извлечение аудио из видео
- Тип данных TypeVarTuple
- Сложные типы данных в Python
- Создание новых списков в Python
- Работа с getopt
- Работа с библиотекой xkcd
- Асинхронное выполнение задач в процессах
- Копирование списков в Python
- Работа с геоданными с помощью geopy
- Отправка POST-запроса в REST API
- Извлечение статей с newspaper3k
- Python 3.12: переиспользование кавычек
- Профилирование с cProfile
- Использование defaultdict в Python
- Импорт модулей и пакетов в Python
- Flask — веб-фреймворк Python
- Ускорение выполнения кода в Python
- Python Enumerate
- Генерация QR-кодов с Python
- Лямбда-функции в Python
- Контроль точности вывода чисел
- Переопределение метода delitem в Python
- Протокол управления контекстом
- Конкатенация списков в Python















