Вопрос Немного по программированию

[Mrhead1996]

"Время доступа к элементам списка O(N), а у массива O(1)", О (N) и О (1) - как понять?

 

[т0ерштп]

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

 

[tino1231]

Я бы посоветовал почитать Кормена "Алгоритмы. Построение и анализ". Не говорю ее всю читать, просто там вначале описана вся эта теория с такой нотацией. О большое, Омега большое и т. д.

 

[саня1234]

Это "big O notation", обозначение временно́й сложности алгоритма. Проще говоря, описывает то насколько быстр алгоритм. ‎ O - линейная зависимость времени выполнения от количества элементов. Обычно такая сложность у перебора всех элементов. O(1) - постоянное время выполнения (независимо от количества элементов). Обычно такая сложность у взятия элемента по его индексу.

 

[den5246]

допустим на доступ к элементу уходит 2 секунды, тогда если мы обратиться ко второму элементу пройдет 4 секунды. к 3му 6. к Nтэму элементу уйдет 2n секунд. это O. О (1) это значит что и к первому и к Nтэму элементу ты доберешься за 2 секунды. Это хватит для приблизительного понимая. Но это не совсем грамотное описание

 

[KPOKyC]

если элементов будет в 1000 раз больше, то время доступа к списку увеличится в 1000 раз, а время доступа к массиву увеличится в 1 раз, т. е не изменится Не буквально, но суть такая