История изменений

Исправление dataman, 05.06.25 22:19 (текущая версия) :

Мой ответ 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;
}

complexityN	ns/op	op/s	err%	total	benchmark
10	109.49	9,133,388.19	2.9%	0.01	`vector erase`
20	178.88	5,590,452.07	1.2%	0.02	`vector erase`
50	364.27	2,745,215.41	3.2%	0.04	`vector erase`
100	676.74	1,477,672.73	1.4%	0.08	`vector erase`
200	1,300.63	768,855.51	0.2%	0.16	`vector erase`
500	3,217.13	310,835.77	0.6%	0.39	`vector erase`
1,000	6,371.71	156,943.72	0.2%	0.76	`vector erase`

coefficient	err%	complexity
6.3936793e-09	2.1%	O(n)
6.5817043e-10	12.0%	O(n log n)
6.7992260e-12	43.7%	O(n^2)
6.6801693e-15	61.1%	O(n^3)
3.1984146e-07	92.1%	O(log n)
1.7455504e-06	122.4%	O(1)

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

Исходная версия dataman, 05.06.25 21:49:

Мой ответ 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;
}

complexityN	ns/op	op/s	err%	total	benchmark
10	109.49	9,133,388.19	2.9%	0.01	`vector erase`
20	178.88	5,590,452.07	1.2%	0.02	`vector erase`
50	364.27	2,745,215.41	3.2%	0.04	`vector erase`
100	676.74	1,477,672.73	1.4%	0.08	`vector erase`
200	1,300.63	768,855.51	0.2%	0.16	`vector erase`
500	3,217.13	310,835.77	0.6%	0.39	`vector erase`
1,000	6,371.71	156,943.72	0.2%	0.76	`vector erase`

coefficient	err%	complexity
6.3936793e-09	2.1%	O(n)
6.5817043e-10	12.0%	O(n log n)
6.7992260e-12	43.7%	O(n^2)
6.6801693e-15	61.1%	O(n^3)
3.1984146e-07	92.1%	O(log n)
1.7455504e-06	122.4%	O(1)

Победитель – 6.3936793e-09 2.1% O(n).