Какая временная сложность поиска в обычном массиве
Перейти к содержимому

Какая временная сложность поиска в обычном массиве

  • автор:

Сложность алгоритмов поиска

Author24 — интернет-сервис помощи студентам

1) Какая асимптотическая сложность бинарного поиска в отсортированном двусвязном списке размера n?

а) О(log n)
б) О(n*log n)
в) О(n^2)
г) О(n)

2) Какая асимптотическая сложность бинарного поиска в отсортированном массиве размера n?

а) О(n)
б) О(log n)
в) О(n*log n)
г) О(n^2)

3) Какая асимптотическая сложность следующего алгоритма на псевдокоде. Дан массив array из n элементов (нумерация с 0 по n — 1):
integer my_mega_calc (integer[] array) integer result = 0;
for (integer x = 0; x < n - 1; x = x + 1)for (integer y + x; y > max(x — 1000, 0); y = y — 1) result = result + array[y];
>
>
return result;
>

4) Какая средняя средняя асимптотическая сложность поиска в хеш-таблице (либо в ассоциативной хеш-таблицу), где n — кол-во элементов в таблице

5) Какова временная сложность поиска в обычном массиве?

Лучшие ответы ( 1 )
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
Ответы с готовыми решениями:

Сложность алгоритмов
Дана строка длины n, состоящая из 0 и 1. Необходимо найти длину её наибольшей подстроки, состоящей.

Сложность алгоритмов
Добрый день, пытаюсь оценить сложность алгоритмов, но возникли сомнения в правильности рассчетов.

Сложность алгоритмов
Оценить временную сложность алгоритма выбора лучшего хода в русских шашках.

Сложность алгоритмов
За какую асимптотику можно решить данную задачу? На вход подаётся список из 100 элементов.

3553 / 2156 / 568
Регистрация: 02.09.2015
Сообщений: 5,441

Лучший ответ

Сообщение было отмечено DimaMik как решение

Решение

DimaMik, 1 — г, 2 — б, 3 — в, 4 — а, 5 — а.

Эксперт Java

3639 / 2971 / 918
Регистрация: 05.07.2013
Сообщений: 14,220
Насчёт хэштаблицы — я бы сказал о(logn)
3553 / 2156 / 568
Регистрация: 02.09.2015
Сообщений: 5,441

ЦитатаСообщение от xoraxax Посмотреть сообщение

Знай сложности алгоритмов

Эта статья рассказывает о времени выполнения и о расходе памяти большинства алгоритмов используемых в информатике. В прошлом, когда я готовился к прохождению собеседования я потратил много времени исследуя интернет для поиска информации о лучшем, среднем и худшем случае работы алгоритмов поиска и сортировки, чтобы заданный вопрос на собеседовании не поставил меня в тупик. За последние несколько лет я проходил интервью в нескольких стартапах из Силиконовой долины, а также в некоторых крупных компаниях таких как Yahoo, eBay, LinkedIn и Google и каждый раз, когда я готовился к интервью, я подумал: «Почему никто не создал хорошую шпаргалку по асимптотической сложности алгоритмов? ». Чтобы сохранить ваше время я создал такую шпаргалку. Наслаждайтесь!

Поиск

Сортировка

Структуры данных

Кучи

Представление графов

Пусть дан граф с |V| вершинами и |E| ребрами, тогда

Нотация асимптотического роста

  1. (О — большое) — верхняя граница, в то время как (Омега — большое) — нижняя граница. Тета требует как (О — большое), так и (Омега — большое), поэтому она является точной оценкой (она должна быть ограничена как сверху, так и снизу). К примеру, алгоритм требующий Ω (n logn) требует не менее n logn времени, но верхняя граница не известна. Алгоритм требующий Θ (n logn) предпочтительнее потому, что он требует не менее n logn (Ω (n logn)) и не более чем n logn (O(n logn)).
  2. f(x)=Θ(g(n)) означает, что f растет так же как и g когда n стремится к бесконечности. Другими словами, скорость роста f(x) асимптотически пропорциональна скорости роста g(n).
  3. f(x)=O(g(n)). Здесь темпы роста не быстрее, чем g (n). O большое является наиболее полезной, поскольку представляет наихудший случай.

Короче говоря, если алгоритм имеет сложность __ тогда его эффективность __

График роста O — большое

  • алгоритмы
  • асимптотический анализ алгоритмов

Какая временная сложность поиска в обычном массиве

Цель данной работы:

2. Краткие сведения из теории

В этой и нескольких последующих лабораторных работах будут рассматриваться способы хранения множества однотипных элементов. Основными критериями сравнения этих способов будут временные сложности алгоритмов поиска/добавления/удаления элементов множества. Главная задача авторов – показать различные способы организации хранения множества однотипных элементов. Также хотелось бы, чтобы читатель почувствовал взаимную зависимость способов хранения данных и сложности алгоритмов их обработки, понял важность изначального выбора структуры данных и алгоритмов их обработки, удовлетворяющей всем необходимым требованиям, следующим из особенностей эксплуатации программного продукта.

Хоть эта глава и называется «методы поиска» интерес представляют и операции добавления и удаления элементов. Эти операции представляют интерес, так как в реальных задачах редко встречается статическое множество, то есть множество, которое не меняется. Далее будет видно, как сильно зависят друг от друга способ хранения множества элементов и сложности перечисленных операций.

Начнем рассмотрение способов хранения множества однотипных элементов с точки зрения алгоритмов поиска/добавления/удаления с алгоритма линейного поиска.

2.1. Линейный (последовательный) поиск

Линейный поиск – самый простой из известных. Суть его заключается в следующем. Множество элементов просматривается последовательно в некотором порядке, гарантирующем, что будут просмотрены все элементы множества (например, слева направо). Если в ходе просмотра множества будет найден искомый элемент, просмотр прекращается с положительным результатом; если же будет просмотрено все множество, а элемент не будет найден, алгоритм должен выдать отрицательный результат. Именно так поступает человек, когда ищет что-то в неупорядоченном множестве. Например, при поиске нужной визитки в некотором неупорядоченном множестве визиток человек просто перебирает все визитки в поисках нужной.

Оформим описанный алгоритм в виде кусочка программы на Паскале. Пусть множество хранится в первых n элементах массива A. При этом не важен тип элементов множества, важна лишь возможность проверки эквивалентности элемента множества искомому элементу Key.

i := 1; while (i<=n)and(A[i]<>Key) do Inc(i); if A[i]=Key then else ;

В среднем этот алгоритм требует n/2 итераций цикла. Это означает сложность алгоритма поиска T(n). Единственное требование к способу хранения множества – существование некоторого порядка на множестве: чтобы можно было указать, что один элемент предшествует другому. Здесь можно хранить множество как в массиве (рассмотренный выше кусок программы), так и в обычном однонаправленном списке:

Type PListItem = ^TListItem; TListItem = record Item: TItem; Next: PListItem; end;

Рассмотрим добавление элемента Key во множество, хранимое в виде массива. Здесь достаточно просто дописать новый элемент в «конец» множества:

Inc(n); A[n] := Key;

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

i := 1; while (i<=n)and(A[i]<>Key) do Inc(i); if A[i]=Key then begin while i Inc(i); end; Dec(n); end;

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

2.2. Быстрый последовательный список

Этот метод поиска является небольшим усовершенствованием предыдущего. В любой программе, имеющей циклы, наибольший интерес представляет оптимизация именно циклов, то есть сокращение числа действий в них. Посмотрим на алгоритм линейного поиска (программу раздела 2.1.). В цикле while производится два сравнения: (i<=n) и (A[i]<>Key). Избавимся от одного из них (от первого), положив A[n+1] := Key. Тогда программа поиска будет выглядеть так:

A[n+1] := Key; i := 1; while A[i]<>Key do Inc(i); if i else ;

Надо сказать, что хотя такой фрагмент кода будет работать быстрее, но его теоретическая сложность остается такой же – T(n). Гораздо больший интерес представляют методы, не только работающие быстро, но и дающие лучшую теоретическую сложность. Один из таких методов – дихотомический поиск.

2.3. Дихотомический (бинарный) поиск

Этот метод поиска предполагает, что множество хранится, как некоторая отсортированная (например, по возрастанию) последовательность элементов, к которым можно получить прямой доступ посредством индекса. Фактически речь идет о том, что множество хранится в массиве и этот массив отсортирован.

Суть метода заключается в следующем. Областью поиска (l, r) назовем часть массива с индексами от l до r, в которой предположительно находится искомый элемент. Сначала областью поиска будет часть массива (l, r), где l=1, а r=n, то есть вся заполненная элементами множества часть массива. Теперь найдем индекс среднего элемента m=(l+r) div 2. Если Key>A[m], то можно утверждать (поскольку массив отсортирован), что если Key есть в массиве, то он находится в одном из элементов с индексами от m+l до r, следовательно, можно присвоить l=m+1, сократив область поиска. В противном случае можно положить r=m. На этом заканчивается первый шаг метода. Остальные шаги аналогичны.

На каждом шаге метода область поиска будет сокращаться вдвое. Как только l станет равно r, то есть область поиска сократится до одного элемента, можно будет проверить этот элемент на равенство искомому и сделать вывод о результате поиска.

Запишем все сказанное в виде программы:

l := 1; r := n; while (l<>r) do begin m := (l+r) div 2; if Key>A[m] then l := m+1 else r := m; end; if A[l]=Key then else ;

Как уже было сказано, область поиска на каждом шаге сокращается вдвое, а это означает сложность T(log(n)).

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

Чтобы при добавлении массив остался отсортированным, новый элемент должен быть вставлен в массив так, чтобы ему предшествовали меньшие элементы, а за ним следовали большие. То есть элементы, стоящие в месте вставки и за ним до конца массива должны быть сдвинуты на одну позицию в сторону конца массива:

i := n; while (i>=1)and(A[i]>Key) do begin A[i+1] := A[i]; Dec(i); end; A[i+1] := Key; Inc(n);

Такая операция добавления имеет сложность T(n).

Удаление в том виде, в каком оно записано в разделе 2.1. сохраняет массив отсортированным.

2.4. Интерполяционный поиск

Рассмотрим еще один метод, имеющий хорошую теоретическую сложность. Как и предыдущий, этот метод предполагает, что множество хранится в массиве и массив отсортирован. Как и предыдущий метод, этот на каждом шаге своей работы сокращает область поиска. Но в отличие от предыдущего метода проба берется не в середине рассматриваемой области.

Пусть имеется область поиска (l, r). Предположим, что элементы множества – целые числа, возрастающие в арифметической прогрессии. Тогда искомый элемент должен находится в массиве (если он вообще там есть) под индексом

(Это следует из свойств арифметической прогрессии)

В этом элементе и будем брать пробу.

l := 1; r := n; while (l<>r) do begin m := l+(r-l)*(Key-A[l])/(A[r]-A[l]); if Key>A[m] then l := m+1 else r := m; end; if A[l]=Key then else ;

Мы сделали очень большое допущение, предположив, что элементы массива представляют собой возрастающую арифметическую прогрессию. В реальности такая ситуация встречается редко. Но этот метод хорошо работает для любых пусть не идеально, но более-менее равномерно распределенных данных. Если же мы имеем дело с неравномерно распределенными данными, то интерполяционный поиск может увеличить число шагов по сравнению с дихотомическим поиском. Теоретическая сложность интерполяционного поиска – T(log(log(n))). Это, конечно, лучше, чем сложность дихотомического поиска, но эти преимущества становятся достаточно заметными лишь при очень больших значениях n. Практически на всех реальных n разница между дихотомическим и интерполяционным поиском по скорости не существенна.

Добавление и удаление можно реализовать так же, как при дихотомическом поиске. К этим операциям предъявляется то же требование: они должны сохранять массива отсортированным.

2.5. Сравнение рассмотренных методов

Метод
поиска

Хранение в массиве

Хранение в списке

Оценка сложности алгоритмов, или Что такое О(log n)

Если вы всё ещё не понимаете, что такое вычислительная сложность алгоритмов, и ждете простое и понятное объяснение, — эта статья для вас.

Обложка поста Оценка сложности алгоритмов, или Что такое О(log n)

Наверняка вы не раз сталкивались с обозначениями вроде O(log n) или слышали фразы типа «логарифмическая вычислительная сложность» в адрес каких-либо алгоритмов. И если вы хотите стать хорошим программистом, но так и не понимаете, что это значит, — данная статья для вас.

Оценка сложности

Сложность алгоритмов обычно оценивают по времени выполнения или по используемой памяти. В обоих случаях сложность зависит от размеров входных данных: массив из 100 элементов будет обработан быстрее, чем аналогичный из 1000. При этом точное время мало кого интересует: оно зависит от процессора, типа данных, языка программирования и множества других параметров. Важна лишь асимптотическая сложность, т. е. сложность при стремлении размера входных данных к бесконечности.

Допустим, некоторому алгоритму нужно выполнить 4n3 + 7n условных операций, чтобы обработать n элементов входных данных. При увеличении n на итоговое время работы будет значительно больше влиять возведение n в куб, чем умножение его на 4 или же прибавление 7n . Тогда говорят, что временная сложность этого алгоритма равна О(n3) , т. е. зависит от размера входных данных кубически.

Использование заглавной буквы О (или так называемая О-нотация) пришло из математики, где её применяют для сравнения асимптотического поведения функций. Формально O(f(n)) означает, что время работы алгоритма (или объём занимаемой памяти) растёт в зависимости от объёма входных данных не быстрее, чем некоторая константа, умноженная на f(n) .

Примеры

O(n) — линейная сложность

Такой сложностью обладает, например, алгоритм поиска наибольшего элемента в не отсортированном массиве. Нам придётся пройтись по всем n элементам массива, чтобы понять, какой из них максимальный.

O(log n) — логарифмическая сложность

Простейший пример — бинарный поиск. Если массив отсортирован, мы можем проверить, есть ли в нём какое-то конкретное значение, методом деления пополам. Проверим средний элемент, если он больше искомого, то отбросим вторую половину массива — там его точно нет. Если же меньше, то наоборот — отбросим начальную половину. И так будем продолжать делить пополам, в итоге проверим log n элементов.

O(n2) — квадратичная сложность

Такую сложность имеет, например, алгоритм сортировки вставками. В канонической реализации он представляет из себя два вложенных цикла: один, чтобы проходить по всему массиву, а второй, чтобы находить место очередному элементу в уже отсортированной части. Таким образом, количество операций будет зависеть от размера массива как n * n , т. е. n2 .

Бывают и другие оценки по сложности, но все они основаны на том же принципе.

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

Аналогично проводят оценку и по памяти, когда это важно. Однако алгоритмы могут использовать значительно больше памяти при увеличении размера входных данных, чем другие, но зато работать быстрее. И наоборот. Это помогает выбирать оптимальные пути решения задач исходя из текущих условий и требований.

Наглядно

Время выполнения алгоритма с определённой сложностью в зависимости от размера входных данных при скорости 106 операций в секунду:

Оценка сложности алгоритмов, или Что такое О(log n) 1

Если хочется подробнее и сложнее, заглядывайте в нашу статью из серии «Алгоритмы и структуры данных для начинающих».

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *