LINUX.ORG.RU

сложность удаления из вектора по значению

 ,


0

5

Есть код c++11:

#include <iostream>
#include <vector>

int main()
{
    std::vector<int> a{1,2,3,4,5,6,7,8,9};
    
    for(auto it=a.begin(); it!=a.end();)
    {
        if (*it % 2)
        {
            it=a.erase(it);
        }
        else
        {
            ++it;
        }
    }

    for(auto& i:a)std::cout<<i<<',';
}

Какая сложность алгоритма?)

Мой ответ O(N). Ответ интервьюера O(N*N), т.к. после каждого удаления вектор «перестраивается или что».


Ответ на: комментарий от bugfixer

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

Tark ★★
()
Ответ на: комментарий от AntonI

ковидиссидента и сторонника теории заговора большой фармы, не асилившего понятие размерности

Реквестирую ссылку на ДРАМУ.

thunar ★★★★★
()
Ответ на: комментарий от thunar

Каменоломня древних ануннаков? (комментарий)

и вниз по треду. Сухая выжимка (букофф там много):

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

AntonI ★★★★★
()
Ответ на: комментарий от Tark

Понятно что это была попытка завязать дискуссию и оценить мировоззрения кандидата.

Но идея за временными векторами крайне сомнительна: к тому моменту как вы будете знать требуемую длину у меня уже будет упакованный вектор с опцией просто обрезать его in-place (resize()), создать новый и swap-in, или resize() + shrink_to_fit(). И вовсе не факт что мне захочется заморачиваться с лишними аллокациями - они однозначно будут стОить, а вот что я за это получу - большой вопрос: сильно зависит от числа удалённых элементов и деталей имплементации аллокатора.

bugfixer ★★★★★
()
Ответ на: комментарий от bugfixer

мировоззрение кандидата в этом мире никому не интересно.

а интересно гипотетически «что выведет код», который никто в здравом уме никогда до промышленной системы не допустит.

пмсм, все гипотетические предпосылки необходимо проверять на практике. Писать модульные тесты и т.д., насколько бы ты ни был опытен и уверен в знании стандартов и поведении компилятора.

но это так, эмоции…

zudwa
() автор топика
Ответ на: комментарий от zudwa

мировоззрение кандидата в этом мире никому не интересно.

Глубочайшее заблуждение. Поверьте на слово человеку в прошлом непосредственно и активно вовлечённому в процесс.

bugfixer ★★★★★
()
Ответ на: комментарий от theNamelessOne

Что тогда ты хотел этим бенчмарком показать-то?

Что бессонница влияет на фейлы.
Что ж, это не самое глупое, что видел LOR.

dataman ★★★★★
()
Ответ на: комментарий от AntonI

Достаточно одного прохода с убегающим и догоняющим индексами

и единичного удаления в конце хвоста от следующего после догоняющего

[upd] фактически это классическая «сборка мусора» сжатие живых на последовательности одним проходом где фильтрующее условие без сохранения внешних адресов у элементов

qulinxao3 ★☆
()
Последнее исправление: qulinxao3 (всего исправлений: 1)
Ответ на: комментарий от GPFault

пока разбирался как же грамотно сделать инциализацию в nanobench

В Гугловской Benchmark есть и https://google.github.io/benchmark/user_guide.html#setupteardown и https://google.github.io/benchmark/user_guide.html#asymptotic-complexity.

Но я больше не буду пробовать. :)

dataman ★★★★★
()
Ответ на: комментарий от qulinxao3

Да, такого мне в голову не приходило.

Но вообще у нас в таких ситуациях вектор выступает как коллекция, т.е. при удалении элементов можно порядок оставшихся не сохранять. Это совсем просто руками делается.

AntonI ★★★★★
()

Половине комментаторов можно посоветовать найти себе другую профессию, ведь вместо обращения к документации они начинают гадать и придумывать гипотетические сценарии.

buddhist ★★★★★
()
Ответ на: комментарий от Obezyan

кста вы путаете амортизационный анализ и оценку(как можно более асимптотически точную) сверху которую и обозначают через O(некая функция)

зы - нотация достаточно кривая о сигма тета - что слегка запутывает особенно когда ознакамливающие очередные «сол мол вилька тарелька думают и ЭТО НАДО ЗАПОМНИТЬ соль моль вилка тарелка при письме»

qulinxao3 ★☆
()

Можно удалять из вектора за O(1) и без тонн копирований - учитесь молодёжь:

  • переставляем местами удаляемый с последним
  • делаем pop_back()
lesopilorama
()
Последнее исправление: lesopilorama (всего исправлений: 1)

Ещё одно доказательство, что ИИ уже умней людей.

In the worst case, the loop can perform up to n erasures (where n is the size of the vector). Each erase on a std::vector is O(n) in the worst case because all subsequent elements must be shifted. Consequently, the overall time complexity is O(n^2).

vbr ★★★★★
()
Последнее исправление: vbr (всего исправлений: 1)
Ответ на: комментарий от lesopilorama

обобщи на удаление набора разрозненных индексов

желательно кодом языка для которого есть программа исполнитель/транслятор

удачи!

qulinxao3 ★☆
()

Сложность удаления k-го элемента равна N-k. Сложность всех удалений при выборе четных числе-это сумма арифметической прогрессии от 0 до N - 2 c шагом 2, то есть, ((N-2)N)/4. Плюс N/2 итераций без удаления, и общее количество операци2 составит (NN)/4. Так что O(N*N)

slew
()
Последнее исправление: slew (всего исправлений: 1)
Ответ на: комментарий от slew

чётность не индекса , чётность значения

следовательно случаи на краях нечего удалять , удалить каждый элемент

худший случай N удалений - стоимость удаления текущая длина массива - следовательно сумма натуральных откидывая меньшие степени О(от квадрата)

ибо код кривой

qulinxao3 ★☆
()
Для того чтобы оставить комментарий войдите или зарегистрируйтесь.