Nano Hash - криптовалюты, майнинг, программирование

Временная сложность для N операций вставки в отсортированный массив

Если у нас есть отсортированный массив, содержащий N элементов, и мы хотим выполнить N операций вставки, то какова должна быть временная сложность наихудшего случая наилучшего подхода?

Я думаю, что это должно быть O (N log (2N)), потому что мы можем вставить N элементов непосредственно в конец отсортированного массива. После всех вставок у нас будет 2N элементов, и мы можем выполнить стабильный алгоритм сортировки всего массива 2N, который займет O (2N log (2N)) ~ O (N log (2N))

Итак, всего = N вставок + сортировка = O (N + 2N log (2N)) = O (N log (2N))

Но везде, где я вижу связанную концепцию, она задается как O (N ^ 2), поскольку они сохраняют сортировку массива после каждой вставки, создавая пространство для каждой вставки между отсортированным массивом!

Мой подход неверен? Должны ли мы сохранять отсортированный массив после каждой вставки? Если да, то означает ли это, что «сохраняет структуру данных неизменной после каждой операции, а не делает ее неповрежденной после целой серии одной и той же операции». Правило действительно для всех структур данных?!

arrays data-structures time-complexity
13.11.2017

  • Должны ли мы сохранять отсортированный массив после каждой вставки? Я не знаю. Что говорят требования? И нет, не все упорядоченные структуры данных имеют одно и то же правило. Сбалансированное бинарное дерево поиска, например, позволяет выполнять вставку за O(log n). 13.11.2017

Ответы:


1

Зависит от того, что вам нужно.

Если вам нужно делать какие-то операции после каждой вставки, то O(n^2) является стандартным (нахождение нужного места O(lgn) и смещение элементов O(n)).

Если вам не нужно ничего делать между вставками, вставьте все элементы в конец и отсортируйте по O(nlgn), чтобы вся операция заняла O(nlgn) (при условии, что вставка в конце занимает O(1) времени).

Кстати, это будет O(nlg(n)), потому что O(nlg(2n)) = O(nlgn + nlg(2)) = O(nlgn + n) = O(nlgn)

13.11.2017
  • Если вам нужно выполнить какие-то операции после каждой вставки, то O(n^2) является стандартным (нахождение нужного места O(lgn) и смещение элементов O(n)). Это звучит неправильно. Разве это не должно быть O (n * logn), а не O (n ^ 2), если вы выполняете одну операцию O (logn), за которой следует операция O (n)? 04.03.2020
    • Новые материалы
    Кластеризация: более глубокий взгляд
    Кластеризация — это метод обучения без учителя, в котором мы пытаемся найти группы в наборе данных на основе некоторых известных или неизвестных свойств, которые могут существовать. Независимо от..
    Как написать эффективное резюме
    Предложения по дизайну и макету, чтобы представить себя профессионально Вам не позвонили на собеседование после того, как вы несколько раз подали заявку на работу своей мечты? У вас может..
    Частный метод Python: улучшение инкапсуляции и безопасности
    Введение Python — универсальный и мощный язык программирования, известный своей простотой и удобством использования. Одной из ключевых особенностей, отличающих Python от других языков, является..
    Как я автоматизирую тестирование с помощью Jest
    Шутка для победы, когда дело касается автоматизации тестирования Одной очень важной частью разработки программного обеспечения является автоматизация тестирования, поскольку она создает..
    Работа с векторными символическими архитектурами, часть 4 (искусственный интеллект)
    Hyperseed: неконтролируемое обучение с векторными символическими архитектурами (arXiv) Автор: Евгений Осипов , Сачин Кахавала , Диланта Хапутантри , Тимал Кемпития , Дасвин Де Сильва ,..
    Понимание расстояния Вассерштейна: мощная метрика в машинном обучении
    В обширной области машинного обучения часто возникает необходимость сравнивать и измерять различия между распределениями вероятностей. Традиционные метрики расстояния, такие как евклидово..
    Обеспечение масштабируемости LLM: облачный анализ с помощью AWS Fargate и Copilot
    В динамичной области искусственного интеллекта все большее распространение получают модели больших языков (LLM). Они жизненно важны для различных приложений, таких как интеллектуальные..