Какая ассимптотическая сложность «доступ по произвольному индексу в двусвязном списке»?

Question

[MichailNikiforov]

Добрый день!

Подскажите, какая ассимптотическая сложность операции "доступ по произвольному индексу в двусвязном списке", используя O-нотацию.

Спасибо!

Answer 1

[GavriKos]

O(n/2) - вам в любом случае надо идти от элемента к элементу, но если индекс больше половины длины - можете начать с конца, и таким образом пройти максимум половину списка.

Comments

[MichailNikiforov]

Будет ли правильней ответить просто O(n)?

[GavriKos]

MichailNikiforov скорее всего нет - потому что тогда нет преимущества в двусвязности списка - O(n) у односвязного

[Mercury13]

> Будет ли правильней ответить просто O(n)
Да, правильней ответить O(n). Ибо по определению символов Ландау константа не в счёт.