Как считать сложность операции сравнения?

Question

zlodiak @zlodiak

Как считать сложность операции сравнения?

#!/usr/bin/env python3

a = [3, 2, 6, 34, 5]    # O(n)
for i in range(5):      # O(n)
    if a[i] > 5:        # ?
        print(a[i])     # O(1)

Помогите пожалуйста посчитать сложность. У меня проблема со строкой:
if a[i] > 5:

как понимаю, здесь придётся оценивать две операции(извлечение из словаря по ключу и сравнение >). Видимо, расчёт сложности для этой строки выглядит так?

O(1) + O(1) = O(2) -> константы сокращаем до единицы -> O(1)

В итоге сложность всего алгоритма получилась такая:

O(n) + O(n) + O(1) + O(1) = O(2n) + O(2) -> константы сокращаем до единицы -> O(2n + 1)

Вопрос задан более трёх лет назад
244 просмотра

6 комментариев

Подписаться 1 Простой 6 комментариев

Roman K @deliro

Зачем тебе всё это вообще? Есть смысл оценивать сложность АЛГОРИТМОВ, а не всех кусков кода.

Написано более трёх лет назад
zlodiak @zlodiak Автор вопроса

Roman Kitaev, а я не вижу разницы :) Ведь алгоритм состоит из строк

Написано более трёх лет назад
Roman K @deliro

P.S. O(2n + 1) — некорректно. Константы выбрасываются. O-нотация показывает РОСТ СЛОЖНОСТИ при увеличении N, а не фактическое количество операций. Так что будет O(n). Вернее даже, будет O(1), потому что твой массив содержит константное количество элементов — 5 штук. Тут нечему вырастать.

Написано более трёх лет назад
Roman K @deliro

zlodiak, Ты занимаешься ерундой, в которой нет практического смысла. Разобраться со сложностью основных структур и алгоритмов — отлично. Ты же пытаешься применить О-нотацию к тому, к чему её нельзя применять. Где у тебя тут N, скажи?

Написано более трёх лет назад
zlodiak @zlodiak Автор вопроса

Roman Kitaev, я правильно понимаю, что учитывать нужно только то, что может возрастать, то есть N. а строки, которые характеризуются только константами(например if a[i] > 5 ) нужно просто игнорировать?

Написано более трёх лет назад
Roman K @deliro

zlodiak, да

Написано более трёх лет назад

Пригласить эксперта

Ответы на вопрос 1

4 комментария

Roman K @deliro

Списки — это массивы. Доступ по индексу за O(1) же

Написано более трёх лет назад
Михаил Макаров @KevlarBeaver

Roman Kitaev, честно говоря, я до настоящего момента думал, что там честный (одно- или двух-) связный список, а оказывается, что немного сложнее. Первое, что на Хабре нашёл:
https://habr.com/ru/post/273045/

Написано более трёх лет назад
Roman K @deliro

Михаил Макаров, я давно понял, что Гвидо его так назвал, чтобы вычислять дилетантов :) С другой стороны, логично же, что доступ по индексу за O(1) у (сколько-угодно-) связных списков не бывает.

Написано более трёх лет назад
longclaps @longclaps
Roman Kitaev, самое обескураживающее, что я по этому поводу видел - это реализация на питоне лисповских списков в лисп-стиле. Чистые функции, много рекурсии, никакого ООП и полный а*уй. Что-то вроде
def push(l, a): return (l, a) def pop(l): tail, a = l return tail, a def getbyidx(l, i): tail, a = pop(l) return getbyidx(tail, i - 1) if i else a def setbyidx(l, i, b): tail, a = pop(l) return (setbyidx(tail, i - 1), a) if i else (tail, b)

Неизгладимое впечатление.
Написано более трёх лет назад

Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации

Похожие вопросы

Python

Простой
Как создать offline карту на python?
- 1 подписчик
- 4 часа назад
- 40 просмотров
0

ответов
Python

Простой
Какие модули есть в Python для целей анализа, форматирования, вывода текста?
- 1 подписчик
- 5 часов назад
- 25 просмотров
1

ответ
Python

+2 ещё

Простой
Как настроить ТГ бота, чтоб кидал посты с пабликов в мой паблик?
- 1 подписчик
- 6 часов назад
- 26 просмотров
0

ответов
Python

+1 ещё

Простой
Как изменить сообщение с текстом на сообщение с картинкой для тг бота в библиотеке py telebot?
- 2 подписчика
- 13 часов назад
- 174 просмотра
2

ответа
Python

+1 ещё

Простой
Пишу телеграм бота на пайтон и вылезает ошибка KeyError: 'recipes'. Как решить?
- 1 подписчик
- 14 часов назад
- 49 просмотров
2

ответа
Алгоритмы

Средний
Справится ли алгоритм с задачей по поиск слов в словаре?
- 1 подписчик
- 14 часов назад
- 56 просмотров
1

ответ
Python

+2 ещё

Простой
Как скрыть данные в кнопке KeyboardButton?
- 2 подписчика
- 15 часов назад
- 59 просмотров
1

ответ
Python

+1 ещё

Простой
Выбор: парсить на питоне с aiohttp, asyncio, bs4 или requests + bs4?
- 1 подписчик
- 21 час назад
- 111 просмотров
2

ответа
Python

+1 ещё

Простой
Почему не срабатывает клик по элементу при открытии станицы selenium python?
- 1 подписчик
- вчера
- 42 просмотра
1

ответ
JavaScript

+1 ещё

Простой
Как подключить кошелёк к web3 сайту?
- 1 подписчик
- вчера
- 73 просмотра
0

ответов
Показать ещё Загружается…

Team Lead (С++, Python)

TopAssistant • Москва

от 400 000 ₽

Python developer

Bell Integrator

До 350 000 ₽

Python developer

Greenway Global • Новосибирск

от 150 000 ₽

Каталог AI tools

18 апр. 2024, в 01:12

150000 руб./за проект

Загрузка характеристик из xml/csv файла в карточки товаров WordPress

18 апр. 2024, в 00:58

5000 руб./за проект

Нарисовать подарки для соц сети

18 апр. 2024, в 00:10

50000 руб./за проект

Зачем тебе всё это вообще? Есть смысл оценивать сложность АЛГОРИТМОВ, а не всех кусков кода.
Roman Kitaev, а я не вижу разницы :) Ведь алгоритм состоит из строк
P.S. O(2n + 1) — некорректно. Константы выбрасываются. O-нотация показывает РОСТ СЛОЖНОСТИ при увеличении N, а не фактическое количество операций. Так что будет O(n). Вернее даже, будет O(1), потому что твой массив содержит константное количество элементов — 5 штук. Тут нечему вырастать.
zlodiak, Ты занимаешься ерундой, в которой нет практического смысла. Разобраться со сложностью основных структур и алгоритмов — отлично. Ты же пытаешься применить О-нотацию к тому, к чему её нельзя применять. Где у тебя тут N, скажи?
Roman Kitaev, я правильно понимаю, что учитывать нужно только то, что может возрастать, то есть N. а строки, которые характеризуются только константами(например if a[i] > 5 ) нужно просто игнорировать?

Answer 1 · 2019-02-16 23:10:16

Это не словарь, а список. Пишут, что в питоне доступ к элементу по индексу имеет сложность O(1), уж не в курсе, как в нём списки реализованы.

Как считать сложность операции сравнения?

Войдите, чтобы написать ответ

Минуточку внимания

Войдите на сайт