Все сервисы Хабра
Сообщество IT-специалистов
Ответы на любые вопросы об IT
Профессиональное развитие в IT
Закрыть
Задать вопрос
MichailNikiforov
@MichailNikiforov
Алгоритмы
Теория
Какая ассимптотическая сложность «доступ по произвольному индексу в двусвязном списке»?
Добрый день!
Подскажите, какая ассимптотическая сложность операции "доступ по произвольному индексу в двусвязном списке", используя O-нотацию.
Спасибо!
Вопрос задан
более трёх лет назад
427 просмотров
Комментировать
Подписаться
2
Оценить
Комментировать
Facebook
Вконтакте
Twitter
Решения вопроса
1
GavriKos
@GavriKos
O(n/2) - вам в любом случае надо идти от элемента к элементу, но если индекс больше половины длины - можете начать с конца, и таким образом пройти максимум половину списка.
Ответ написан
более трёх лет назад
3
комментария
Нравится
1
3
комментария
Facebook
Вконтакте
Twitter
MichailNikiforov
@MichailNikiforov
Автор вопроса
Будет ли правильней ответить просто O(n)?
Написано
более трёх лет назад
GavriKos
@GavriKos
MichailNikiforov
скорее всего нет - потому что тогда нет преимущества в двусвязности списка - O(n) у односвязного
Написано
более трёх лет назад
Mercury13
@Mercury13
> Будет ли правильней ответить просто O(n)
Да, правильней ответить O(n). Ибо по определению символов Ландау константа не в счёт.
Написано
более трёх лет назад
Пригласить эксперта
Ответы на вопрос
0
Ваш ответ на вопрос
Войдите, чтобы написать ответ
Войти через центр авторизации
Похожие вопросы
Алгоритмы
+1 ещё
Средний
Как можно предиктить дату регистрации при массиве данных?
1 подписчик
03 июл.
86 просмотров
1
ответ
Программирование
+1 ещё
Простой
Как работает регистрация и аутентификация с помощью ЭЦП?
1 подписчик
26 июн.
183 просмотра
3
ответа
Компьютерные сети
+1 ещё
Простой
Как построить топологию сетей (данные в FDB таблице) когда связи замкнуты в кольцо?
2 подписчика
25 июн.
454 просмотра
2
ответа
Алгоритмы
Средний
Какие переходы для ДП у «Гелифиш и незабудка» codeforce?
1 подписчик
12 июн.
82 просмотра
1
ответ
C#
+1 ещё
Простой
Почему неправильно работает Keeloq?
1 подписчик
05 июн.
102 просмотра
1
ответ
Алгоритмы
Простой
Какие переходы для ДП Codeforces Петя и пауки?
1 подписчик
27 мая
156 просмотров
1
ответ
Алгоритмы
Простой
Какую букву в игре поле чудес в этом случае лучше всего открыть? правильное ли это решение?
1 подписчик
20 мая
240 просмотров
3
ответа
Python
+3 ещё
Простой
Как повысить точность классификации по табличным документам?
2 подписчика
19 мая
258 просмотров
1
ответ
C#
+1 ещё
Простой
Почему моя реализация Shaker Sort-а такая медленная?
2 подписчика
17 мая
614 просмотров
1
ответ
Алгоритмы
Простой
Какую букву в игре поле чудес в этом случае лучше всего открыть?
1 подписчик
17 мая
248 просмотров
1
ответ
Показать ещё
Загружается…
Вакансии с Хабр Карьеры
Разработчик бэкенда в команду коммуникационной платформы
Яндекс
•
Москва
от 300 000 до 490 000 ₽
Разработчик в буткемп Core Infrastructure
Яндекс
•
Москва
от 300 000 до 490 000 ₽
Разработчик бэкенда сервисов телефонии
Яндекс
•
Москва
от 300 000 до 490 000 ₽
Минуточку внимания
Войдите на сайт
Чтобы задать вопрос и получить на него квалифицированный ответ.
Войти через центр авторизации
Закрыть
Реклама