0
Я читаю лекцию по алгоритму, и он говорит мне, что я могу «искать i-й элемент списка в постоянное время».Почему я могу найти i-й элемент списка в постоянное время?
Может кто-нибудь объяснить, почему это для меня? Не должен ли худший сценарий быть линейным временем O (n), потому что, если i-й элемент находится вне списка? Затем он проходит через все элементы списка и понимает, что отсюда нет O (размер списка: n)?
Дайте мне знать ваши мысли.
Необходимо предоставить больше контекста. «Список» может означать много разных структур данных, и некоторые из них (например, связанные списки) абсолютно не имеют постоянного времени доступа. – CollinD
@CollinD: О, мой плохой, я довольно новый. Это было введение в лекцию по информатике, поэтому мы еще не получили подробный список ссылок. Я предполагаю, что он говорит о регулярных списках. Я получаю это из этой лекции вокруг отметки 2:50: https://www.youtube.com/watch?v=pjLbxB9TXJs – Helene
У меня есть подозрение, что этот профессор использует термин «Список» в качестве standin для ' Array' (возможно, контекст - это Python или некоторый такой язык, который разделяет эту терминологию). Я просто попытаюсь оглянуться на предыдущие лекции для деталей (так как тот, с которым вы связаны, является лекцией 10) – CollinD