2

Какие есть варианты оценки производительности алгоритмов на С++??? P.S. Если можно, с простыми примерами.

4
  • 4
    в целом, с++ не имеет отношения к оценке производительности алгоритмов. Почитайте первый том Кнута - там все хорошо описано.
    – KoVadim
    7 фев 2014 в 8:31
  • 1
    Из банальщины - считать количество сравнений и пересылок. Подсчет трудоемкости. Либо время выполнения засекать.
    – iPro
    7 фев 2014 в 8:33
  • Почитайте Макконнелл Дж. Анализ алгоритмов. 7 фев 2014 в 11:16
  • habrahabr.ru/post/188010
    – Deadkenny
    10 фев 2014 в 7:16

3 ответа 3

3

производительность алгоритмов изучается в науке\предмете "Теория сложности алгоритмов" базисом для сравнения алгоритмов является "big-O notation" (нотация "большое О") помимо этого есть ещё классы сложности (но это совсем другой уровень)

в общем через "big-O notation" измеряется время и объём памяти которое нужно алгоритму, при этом сравнение происходит независимо от языка, железа, нюансов реализации.

по своей сути это "линейка" для алгоритмов, и у этой линейки есть 3-и типа измерения: примерно точное(тета), худший случай из лучших(омега) и самое полезное лучший случай из худших(О).

ну и наконец-то ссылки на хабр

Введение в анализ сложности алгоритмов:

(часть 1)

(часть 2)

(часть 3)

(часть 4)

3

На практике понадобится несколько оценок:

  • O(1) - константное время,
  • O(log(n)) - логарифмическое по основанию 2,
  • O(n) - линейное,
  • O(n log(n)) - линейно-логарифмическое,
  • O(n^2) - квадратичное,
  • а остальные более сложные стоит избегать, если только перемножение матриц не оптимизированным способом O(n^3).

Например O(1) константное время это доступ к массиву по индексу или к хэш-таблице в лучшем случае конечно, так же константное время доступа к мин/макс элемента в бинарной или Фибоначчиевой куче. Например линейный поиск элемента в массиве имеет сложность O(n) то есть само название поиска говорит о линейной сложности, а вот бинарный поиск в упорядоченном массиве имеет сложность O(log(n)) логарифмическую. Тоже самое и с алгоритмами сортировок, быстрая сортировка в лучшем случае даст линейно-логарифмическую сложность O(n log(n)), в худшем может дать квадратичную O(n^2) сложность как обычные сортировки пузырьком/выбором/вставкой. К примеру бинарное двоичное дерево поиска(BST) в не вырожденном дереве все операции имеют сложность O(log(n)) но если дерево станет вырожденным то сложность может станет линейной как в обычном связном списке O(n). Ещё нужно знать в каких алгоритмах используешь дополнительную память, каковы скрытые константы...

1

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

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.