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

естессно при удалении элемента хвост сдвигается на одну позицию влево. ну да примерно N*N

O(1), в коде нет размерности N.

если каждый элемент будет чётным, то на каждой итерации будет сдвигаться N-1 элементов. N*N/2 получается

erase() имеет линейную сложность от размера, находится в цикле по всей длине, очевидно, что O(N*N).

Что бы это работало за O(N) нужно на первом проходе отмечать элементы для удаления, на втором дефрагментировать то что осталось.

А так конечно O(N^2)

Думается мне что интервьюер хотел услышать об remove_if() и почему не стОит изобретать собственные велосипеды.

да. и erase_if.

насколько понимаю, это просто обертки над кодом на C++11 выше.

ИИ так пишет:

Временная сложность erase_if для vector составляет O(N + M), где N - количество удаленных элементов, а M - количество перемещенных элементов. Это связано с тем, что erase_if сначала итерируется по контейнеру, проверяя условие для каждого элемента (это часть сложности O(N)), а затем удаляет элементы, что может потребовать перемещения оставшихся элементов (сложность O(M))

т.е. вообще говоря если N=M -> O(N+M) ~ O(N) :D

к алгоритмам это отношения не имеет. Иди в веб там они вообще не нужны. При поиске какого-то значения в массиве у тебя сложность будет в худшем случае O(N), где N - длина, когда что-то искомое в конце массива. При удалении каждого 2-го элемента (с индексами 1,3,5,7,… нечетного больше 0) там полное копирование же происходит, те внутри реализации вектора проход по вектору производится… Но рассматривается лишь худший случай. Нужен листик и бумага чтобы посчитать количество итераций, но скорее всего он прав.

Мой ответ O(N). Ответ интервьюера O(N*N)

А что «думает» nanobench?

#define ANKERL_NANOBENCH_IMPLEMENT

#include <iostream>
#include <vector>
#include "nanobench.h"

int main() {

    ankerl::nanobench::Bench bench;

    std::vector<int> a;

    for (auto setSize : {10U, 20U, 50U, 100U, 200U, 500U, 1000U}) {
	a.resize(setSize);
	std::iota(a.begin(), a.end(), 0);

	bench.complexityN(setSize).minEpochIterations(10000).run("vector erase", [&] {
	    for(auto it = a.begin(); it != a.end();)
	    {
		if (*it % 2)
		{
		    it = a.erase(it);
		}
		else
		{
		    ++it;
		}
	    }
	    ankerl::nanobench::doNotOptimizeAway(a);
        });

    }
    std::cout << bench.complexityBigO() << std::endl;
}

И Оскар отправляется 6.3936793e-09 2.1% O(n).

А что «думает» nanobench?

А пофиг, что он там думает. N*N и все тут. Анализ работы кешей, особенностей работы алгоритма, пороков nanobench и проч. билиберды к оценкам O(…) не относится.

Понапридумывают методов на каждый чих, а программисту их все помни:-)

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

Из-за того что вектор перестраивается с убывающим количеством элементов то получаем сложность меньше чем квадратичная (N*M), где M<N.

Также понятно что сложность больше линейной N. Отсюда выбираем сложность между линейной и квадратичной, а это логарифмическая.

nanobench не мытьмой, я просто разместил объяву.

Из-за того что вектор перестраивается с убывающим количеством элементов то получаем сложность меньше чем квадратичная (N*M), где M<N.

нет. а если б начали с конца - и «вектор» возрастал бы?

«убывающий вектор» просто дает некий неубывающий вектор средней длины (порядка N/2). и сложность остается «теоретически квадратичной».

просто пересылка данных пачкой намного быстрей пересылки поэлементно - (которая и дает лишнее N), потому теоретический N*N тут близок к N, в силу высокой скорости пересылки пачкой.

а нанобенч лишь показывает насколько эффективно современный процессор выполняет некоторые алгоритмы с теоретической сложностью N*N.

нет. а если б начали с конца - и «вектор» возрастал бы?

возрастал бы до M<N.

сложность остается «теоретически квадратичной».

теоретически.

Тут все дело в том что и N и N квадрат - чёткие границы до которых не дойдёт сложность. Те в обоих случаях нужно поднатянуть сову на глобус чтобы заявить что это линейная или что это квадратичная сложность, понимаете? Реальная сложность между ними.

теоретический N*N тут близок к N

Вы только что подтвердили своими словами мой ответ. Близок к N, но не N, причём теоретически может быть почти до N*N. Это и есть логарифмическая сложность.

Из-за того что вектор перестраивается с убывающим количеством элементов

Сложность становится O(N * (N-1)/2), что эквивалентно O(N*N). Нельзя так лихо оценивать больше-меньше.

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

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

И дело тут вовсе не в «уменьшении длины пересылки», что никак не может дать логарифм, а даст N/2 (опять же на абстрактном проце, для которого и строятся такие рассуждения.).

Нельзя так лихо оценивать больше-меньше.

Смотрите, если вектор содержит вершины пирамиды (линеаризованный объект такой), то в этом случае, если мы удаляем, например, определённый элемент, то сложность будет равна логарифмической. Ну нет там квадрата.

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

Почитайте более внимательно когда возникает логарифмическая сложность.

вернитесь из фантазий на землю, топикстартер вам код нарисовал, где удаляется каждый второй! элемент. по нему и задан вопрос.

если б удалялось ln N элементов, сложность была бы N*ln N. Но это не наш случай.

Скажем по секрету, что если б не удалялся ни один элемент, сложность была бы N.

топикстартер вам код нарисовал, где удаляется каждый второй! элемент. по нему и задан вопрос.

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

и при этом вы заявляете что сложность квадратичная.

а какая еще??? N/2 раз(нечетные) надо переписать N/2 элементов(средняя сдвигаемая длина) на один элемент влево.

N/2 * N/2 дает сложность N*N. :))))

а какая еще??? N/2 раз(нечетные) надо переписать N/2 элементов(средняя сдвигаемая длина) на один элемент влево.

последний элемент - нечетный, удаляем нечетные числа, т.е. (N-1)/2.

итоговая сложность N*(N-1)/2 => N^2 - N что явно меньше квадратичной, но больше линейной. Отбрасывать N позволительно мидлам которые про биг О на хабре читали.

тимлид, вы не можете это понять, и занимаетесь балабольством на самом деле

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

С каких это пор логарифмическая сложность расположилась между линейной и квадратичной?

Вообще-то O(log n) < O(n) < O(n²)

итоговая сложность N*(N-1)/2 => N^2 - N что явно меньше квадратичной, но больше линейной. Отбрасывать N позволительно мидлам которые про биг О на хабре читали.

посмотрите уже как оценивается сложность и не порите чушь. N^2-N…такой просто не бывает :) сложность оценивается асимптотически. и N^2 забивает N.

начните отсюда, сеньор.

https://ru.wikipedia.org/wiki/%D0%92%D1%80%D0%B5%D0%BC%D0%B5%D0%BD%D0%BD%D0%B0%D1%8F_%D1%81%D0%BB%D0%BE%D0%B6%D0%BD%D0%BE%D1%81%D1%82%D1%8C_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D0%B0

Ну вот зачем?!! Зачем вы мешаете Обезьяну выводить всех этих знатоков на чистую воду? Никто из них даже не заметил, видите как тужатся доказывая.

Вы даже не заметили то о чем написал @Gordon, миддл ;)

у обезяна речь идет о n*ln n. а не чисто логарифме. и то, он ее приплел сюда от непонимания самого термина, и как его оценивают.

Вы даже не заметили то о чем написал @Gordon, миддл ;)

этот вообще в ваших потемках заблудился. а O(N^2 - N) - это надо отлить в граните, сеньор :)

шепотом: я знаю

При оч малых N можно считать что n*ln N ~ n, это как раз наш случай

;)

При оч малых N можно считать что n*ln N ~ n, это как раз наш случай

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

сложность оценивается асимптотически. и N^2 забивает N.

на больших N. У нас N какое, большое? Пример же дан чётко с небольшим количеством значений.

никого не интересует сложность при малых.

Дан пример где чётко определено небольшое N. Если бы это было не так написали бы

std::vector<int> a{1,2,3,4,5,6,7,8,9,.., n};

Тогда ваши рассуждения были бы верны.

Вы отбрасываете явное условие в задаче.

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

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

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

посоветуйте ему там написать хотя бы 10^ элементов, чтобы не позориться.

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

Нет, нельзя, надо задать уточняющий вопрос, но у нас такой возможности нет.

Вы хорошо держитесь, но это вам не поможет ;)

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

насколько понимаю, это просто обертки над кодом на C++11 выше.

Вообще говоря std::remove_if() вполне себе полновесный самостоятельный алгоритм которому «100 лет в обед»: в 98ых плюсах уже был. std::erase_if() - да, относительно молодая (cxx-20) обёртка над ним прибивающая хвост (что раньше приходилось делать «ручками»).

Вы хорошо держитесь, но это вам не поможет ;)

Мне не надо помогать, я даже не напрягаюсь :) Удивительно детские вопросы приходится обсуждать с сеньорами.

https://t.me/profunctor_io/10941

выше отметили что для этой задачи есть более лучшие методы в stl

а конкретно по коду(ибо std::vector<int>.erase обычно двигает хвост ) O(n*n) то бишь квадрат  — «чютка» уменьшить «константу» можно если делать обход с конца :)

но на таком (n=10) не важно

любая реализация (нужного фильтра) очевидно не ниже O(n) ибо требуется проход по массиву

отрицательно комплексное у тут N

Никакого смысла нет обсуждать сложность на фиксированном наборе данных, для такого случая сложность всегда O(1). Это вы тут демагогией занимаетесь.

А что «думает» nanobench?

Поправь меня, если я где-то ошибся (не пишу на C++):

1. Ты выполняешь бенчмарк для разных размеров вектора в цикле.
2. В каждой итерации цикла ты ресайзишь и заполняешь вектор с нуля.
3. Далее ты запускаешь бенчмарк, который замеряет скорость выполнения замыкания; вектор при этом в замыкание передаётся по ссылке. Замеры выполняются дохрениллиард раз (нам не особо важно, сколько именно, главное, что больше 1).
4. В каждой итерации бенчмарка ты удаляешь из вектора чётные элементы.

Если я всё правильно понял, у тебя в первой итерации бенчмарка (не путать с итерацией цикла!) удаляются все чётные элементы вектора, при этом все последующие итерации бенчмарка будут выполняться уже на изменённом векторе, в котором чётных элементов не осталось (т.е. в последующих итерациях бенчмарка будет просто линейный проход по вектору без вызовов erase).

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

Правильный ответ: логарифмическая сложность

Мдя… впрочем чего ещё можно ожидать от ковидиссидента и сторонника теории заговора большой фармы, не асилившего понятие размерности?

В бенче критическая ошибка.

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

Ошибка прикольная, без отладочной печати не нашёл, вам светят большие перспективы на ниве внедрения незаметных бэкдоров))

Вот такое даёт n^2

#define ANKERL_NANOBENCH_IMPLEMENT

#include <iostream>
#include <vector>
#include "nanobench.h"

int main() {

    ankerl::nanobench::Bench bench;

    std::vector<int> a;

    for (auto setSize : {10U, 20U, 50U, 100U, 200U, 500U, 1000U}) {

        bench.complexityN(setSize).minEpochIterations(10000).run("vector erase", [&] {
            a.resize(setSize);
            std::iota(a.begin(), a.end(), 0);
            for(auto it = a.begin(); it != a.end();)
            {
                if (*it % 2)
                {
                    it = a.erase(it);
                }
                else
                {
                    ++it;
                }
            }
            ankerl::nanobench::doNotOptimizeAway(a);
        });

    }
    std::cout << bench.complexityBigO() << std::endl;
}

Собрано c -O3

| complexityN |               ns/op |                op/s |    err% |          ins/op |          cyc/op |    IPC |         bra/op |   miss% |     total | benchmark
|------------:|--------------------:|--------------------:|--------:|----------------:|----------------:|-------:|---------------:|--------:|----------:|:----------
|          10 |               30.91 |       32,347,322.02 |    1.2% |          272.00 |           87.54 |  3.107 |          69.00 |    0.0% |      0.01 | `vector erase`
|          20 |               63.68 |       15,702,760.61 |    1.4% |          516.00 |          178.88 |  2.885 |         137.00 |    0.0% |      0.01 | `vector erase`
|          50 |              217.43 |        4,599,177.12 |    2.0% |        1,632.00 |          607.51 |  2.686 |         373.00 |    0.0% |      0.03 | `vector erase`
|         100 |              560.53 |        1,784,031.31 |    2.0% |        4,431.00 |        1,568.49 |  2.825 |         855.00 |    0.0% |      0.07 | `vector erase`
|         200 |            1,656.03 |          603,854.27 |    0.9% |       13,141.00 |        4,675.86 |  2.810 |       2,080.00 |    0.4% |      0.20 | `vector erase`
|         500 |            8,085.70 |          123,675.13 |    0.8% |       60,715.01 |       23,157.82 |  2.622 |       7,542.01 |    0.7% |      0.97 | `vector erase`
|       1,000 |           31,408.96 |           31,838.05 |    0.5% |      216,916.03 |       89,517.07 |  2.423 |      23,055.03 |    1.3% |      3.77 | `vector erase`

|   coefficient |   err% | complexity
|--------------:|-------:|------------
| 3.1481492e-11 |   3.4% | O(n^2)
| 3.1932491e-14 |  27.7% | O(n^3)
| 2.8805564e-09 |  40.0% | O(n log n)
| 2.7514601e-08 |  52.1% | O(n)
| 1.1735065e-06 | 151.8% | O(log n)
| 6.0033211e-06 | 178.4% | O(1)

По-хорошему чуть тяжёлую подготовку в виде вызова iota надо вынести в функцию setup, вызываемую на каждом цикле, но nanobench пока не придумал подход к этому и она является линейной, не создавая квадратичную сложность.

К алгоритму ТС это вообще никак не относится. Заканчивайте уже позориться, прям стыдно за Вас…:-(

Да всё так, критическая ошибка в бенче. Тоже увидел, но пока разбирался как же грамотно сделать инциализацию в nanobench - опоздал )

сорян ща историю переписывают именно как заг овор

зы. вера не коррелирует с разумом

все «4» комбинации возможны

По-хорошему чуть тяжёлую подготовку в виде вызова iota надо вынести в функцию setup, вызываемую на каждом цикле, но nanobench пока не придумал подход к этому и она является линейной, не создавая квадратичную сложность.

Автор пока предлагает запускать два бенча: один с сетапом и собсно замеряемым кодом, второй — только с сетапом, и потом отнимать от первого результат второго xD

Думается мне что интервьюер хотел услышать об remove_if() и почему не стОит изобретать собственные велосипеды

О remove, если уж по значению