Технологии
Решено
big-O notation - вопрос №327077
здравствуйте.
подскажите, как можно выполнить оценивание метода по big-O notation? т.е. у меня есть программа и мне нужно подсчитать количество операций (время), требуемое на ее выполнение и использовать при этом big-O notation.
программа на c#
август 11, 2012 г.
-
Всего ответов: 1
-
«О большое» это оценка сложности (времени исполнения) алгоритма в зависимости от некоего параметра
http://ru.wikipedia.org/wiki/O-%D0%BD%D0%BE%D1%82%D0%B0%D1%86%D0%B8%D1%8F
условно можно сказать что О это типовой набор операций, который придется повтороть f(n) раз, для нахождения результата алгоритма
наиболее иллюстративный пример это описание трудоемкости алгоритмов факторизации целых чисел в зависимости от их разрядности
менее впечатляющий, но не менее часто встречающийся пример — оценка скорости алгоритмов сортировки в зависимости от размеров массива
можно сказать что О это операция. но надо понимать что это не оператор программы, это может быть весма сложный набор операторов языка программирования
это одна повторяемая операция, это одна итерация в циклическом алгоритме
не имеет значения язык на котором Вы реализуете алгоритм
имеет значение количество циклов его повторения в зависимости от какой то численной характеристики входных данных и формула, которая позволяет предсказать сколько раз надо выполнить циклические проходы алгоритма (в том числе это могут быть разные по функциональности ветви алгоритма или произведение количества вложенных циклов)
при этом формула может быть как строго доказанной, так и эмпирической, если доказательство не известно
так что Ваша задача носит в первую очередь математический характер а не програмно-технический
Лучший ответ по мнению автора
Похожие вопросы