Есть такое понятие как сложность алгоритма относительно n-элементов на входе.
Самая простая техника подсчета сложности - посчитать кол-во циклов и сколько их вложено вдруг в друга.

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

Ну самое типичное классическое попадалово objList.numberOfItems(). const или linear? бывают дурацкие инструменты, где такое есть линеар...

- - - - - - - - -

Классическим инструментом проверки цены функции является итерлям:




Вопрос: какая операция в плюсах может считаться единицей измерения функциональной операции?

Все знают, что sizeof измеряет в char'ах. А что может быть чаром для измерения количества операций. Что может быть попугаем в данном случае?

Бонусный вопрос: является ли подобное операцией вообще?

MasterZivОперация выбирается каждый раз в зависимости от алгоритма, который оценивается.
Например:

Алгоритм "сотрировка" -- операция "ставнение двух элементов" (обычно).

Алгоритм "поиск элемента в коллекции" -- операция "сравнение элемента коллекции и искомого".

Алгоритм "подсчёт элементов коллекции" -- операция "чтение элемента коллекции".

И так далее.


Понятно, спасибо.

Dimitry SibiryakovА что, тупо померять время работы на N=1,2,4,...10500 и потом построить график зависимости
нынче некошерно?


Этот метод замера дает оценку комплексити алгоритма. А вопрос темы был про поиск единицы измерения комплексити для плюсов.

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

Но если у нас есть некая единица измерения (аналог sizeof), то мы можем сказать, что стоимость первой функции 5 попугаев, а стоимость второй функции 35 попугаев. Хотя обе они линейны.

Существует формулировка, которая позволяет нам сказать, что несмотря на на то, что обе функции линейны по комплексити, первая стоит 5n, а вторая стоит 35n, но в этой теме мне сказали, что n для каждой функции всегда будет свое. Например, она функция перебирает инты, а другая строки. Обе могут быть 5n, но первая будет стоит всего 5 попугаев, а вторая целых 75 попугаев.

Вот про что был вопрос.