Алгоритм — удаление части массива

  • В этой теме 0 ответов, 1 участник, последнее обновление 2 недели, 3 дня назад сделано Васильев Владимир Сергеевич.
Просмотр 0 веток ответов
  • Автор
    Сообщения
    • #7043
      @admin
      StudLance.ru

      Нередко возникает задача удаления части массива — это может быть, например, подстрока в строке. При этом удалять эту часть по одному элементу не эффективно. Если удаляемый подмассив состоит из k элементов — то вычислительную сложность всего алгоритма можно оценить как O(n*k). Однако, возможно получить решение с оценкой O(n), для этого достаточно выполнять сдвиг элементов массива не на 1 позицию, а сразу на k. Схема работы такого алгоритма проиллюстрирована на рисунке:

      Удаляемый подмассив выделен красным цветом, при этом для сдвига досточно элементы, расположенные правее этого подмассива переписать на k позиции левее. На рисунке элементы обмениваются местами — это сделано исключительно для наглядности.

      Блок-схема алгоритма:

      StudLance.ru

Просмотр 0 веток ответов
  • Для ответа в этой теме необходимо авторизоваться.
×