Какова сложность вставки в отсортированный список ссылок в нотации "большого О"?
Многие у MVP есть подписки подарка, которые они могут выдать, таким образом, это окупается, чтобы быть видимым в сообществе.
Говорят в Вашей группе локального пользователя, запускаются (или участвуйте) в проекте с открытым исходным кодом запустите, блог... просто обычно получают Ваше имя там.
В конечном счете Вы получите один (или MVP:)).
то, Что я нашел, - то, что, если Вы обращаете внимание, существует много возможностей поймать бесплатный экземпляр Office или Visual Studio в локальных событиях Microsoft.
Удачи!
2 ответа
Подумайте, что за означает однократную вставку в отсортированный список ссылок. У вас есть новый элемент, который должен быть где-то в списке.
1) Вы должны найти нужное место в списке. Это линейный поиск. O (n)
2) Вставить легко: создать новый узел, зафиксировать указатели на предыдущий и следующий узлы. O (1)
В этом случае O (n) перевешивает O (1), поэтому это O (n).
Количество элементов на самом деле не относится к big-O, поскольку все оно основано на на порядки величины.
Во-первых, я бы рекомендовал прочитать статью в Википедии о связанных списках , особенно (небольшую) часть об ускорении поиска.
Теперь, чтобы ответить на ваш вопрос , вставка в связанный список занимает O (1) раз, если вы уже знаете, куда вы хотите его вставить. Поскольку мы говорим о Сортированном связном списке, и вы вставляете, не зная, куда должен идти элемент, это займет у вас O (n) времени (так как вам нужно искать по всему списку чтобы найти место, куда идет элемент). Обратите внимание, что на самом деле добавление элемента - O (1), как я сказал выше.
Обратите внимание, что это не очень эффективный поиск, поскольку поиск в отсортированном массиве, например, занимает время O (lg (n)) (с использованием бинарный поиск). К сожалению, с массивом после нахождения элемента