Оценка времени выполнения программы. 0

Иногда возникает необходимость особенно на олимпиадах оценить время работы алгоритма. По типу » время выполнения этого алгоритма порядка O(N^2*logN) » Как эту величину находить?

это «о» малое от того, что в скобках? Это к Теодору….

ну запись просто такая. Можно так что » время выполнения этого алгоритма порядка N^2*logN »

Нет, это «О большое», то бишь, константа умноженная на то, что в скобках. О малое для программирования — не слишком удобная конструкция.

Оценка же быстодействия алгоритмов — вещь грубая, и точные методы используются только для определения класса задачи — P, NP, и т.д.

Для получения же числа как O(N^2*logN), применяют «палечные» методы. Типа, чтобы убедиться, что в неупорядоченной матрице NxN нет элемента с заданными свойствами, надо перебрать их все. Стало быть, сложность «тупого» алгоритма перебора будет O(N^2).

Посмотри еще здесь:

То есть насколько я понял никаких формул для расчета этого дела нету, просто надо знать что для алгоритмов одного типа значение одно, а для других — другое. Я правильно понял?

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

Ищем число 5 в упорядоченном списке длины N.

Алгоритм 1: Тупо перебираем все элементы «он.не он». Если 5 окажется в самом конце списка, мы сделали N операций. Значит, быстрота алгоритма O(N).

Алгоритм 2: Действуем по принципу «лев в пустыне» — список-то упорядоченный! — делим пустыню пополам, в одной половине лев есть, в другой — нет. Делим список пополам, смотрим на конечные значения. Если 5 между ними — это наш новый список. За K шагов алгоритма список стал в 2^K раз короче, значит, когда 2^K = N, у нас только 1 элемент, и дело сделано за K = logN шагов. Быстрота алгоритма = O(logN).

А с формулами туго, что ты в них подставишь?

Интересно, а есть на форуме профессиональные программисты. Занятно было бы услышать профессиональную оценку моего бреда… :-)

Имхо это не бред.

Ищем число 5 в упорядоченном списке длины N.

Алгоритм 1: Тупо перебираем все элементы «он.не он». Если 5 окажется в самом конце списка, мы сделали N операций. Значит, быстрота алгоритма O(N).

Алгоритм 2: Действуем по принципу «лев в пустыне» — список-то упорядоченный! — делим пустыню пополам, в одной половине лев есть, в другой — нет. Делим список пополам, смотрим на конечные значения. Если 5 между ними — это наш новый список. За K шагов алгоритма список стал в 2^K раз короче, значит, когда 2^K = N, у нас только 1 элемент, и дело сделано за K = logN шагов. Быстрота алгоритма = O(logN).

А с формулами туго, что ты в них подставишь?

Интересно, а есть на форуме профессиональные программисты. Занятно было бы услышать профессиональную оценку моего бреда… :-)

Good Luck,

UT

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

ИМХО, алгоритмизация подстчета для 1 и 2, сильно различны, поскольку количество итераций как таковых мало влияет на время работы процесса этого алгоритма. Пример

десять раз сложить — это быстрее, чем 5 раз умножить.

Так как по представлению сложение\сдвиг и оценки погрешности при переносе разрядов — Умножение в 2 раза медленее. Так же если представленна система команд процессора на умножение(например в архитектуре CISC) то это не ускорит процесс, а скорее увеличит время на выборку адресса инструкции(Схемотехника фарево).

Честно говоря не знаю на сколько уменьшение кол-ва итераций увеличит скорость работы, ведь и степень и логарифм долие для получения двоично-десятичного кода, а следовательно примерно одинаковы по скорости, хотя степень быстрее, но обработка склаживает…разницу. А в матеиатическом представлении — да….наверное, алгоритм 2 быстрее. Хотя я себе туго представляю подсчет «O»…. Но на уровне тактов процессора, ИМХО оба метода примерно равны по скорости (+-100 нс.)

Ну да, это понятно. Именно поэтому в обозначениях «О большое». Т.е., оценка дается не бестродействию алгоритма в сравнении с другими для того же N, а тому, как время его выполнения растет с ростом N.

Если, скажем, f(N) = O(N); g(x) = O(N^2), то ничего невозможно сказать про то, что больше, f(25) или g(25) — или любого другого конкретного N. Единственное, что можно сказать, это что если N увеличить в два раза, то f возрастет в 2 раза, а g возрастет в 4 раза.

«O большое» не подсчитывается. По определению,

где C — произвольная константа, от x не зависящая. В контексте обсуждаемой проблемы — в нее идет время выполнения одной итерации. Разумеется, для разных алгоритмов она разная, поэтому сравнивать разные алгоритмы на этом основании нельзя.

ЗЫ А чей-то ты выкать начал? ;-)

Если, скажем, f(N) = O(N); g(x) = O(N^2), то ничего невозможно сказать про то, что больше, f(25) или g(25) — или любого другого конкретного N. Единственное, что можно сказать, это что если N увеличить в два раза, то f возрастет в 2 раза, а g возрастет в 4 раза.

«O большое» не подсчитывается. По определению,

O(x) = Cx

где C — произвольная константа, от x не зависящая. В контексте обсуждаемой проблемы — в нее идет время выполнения одной итерации. Разумеется, для разных алгоритмов она разная, поэтому сравнивать разные алгоритмы на этом основании нельзя.

Good Luck,

UT

ЗЫ А чей-то ты выкать начал? ;-)

Хорошо объяснил. Понятно. Спасибо. А вникать я начал потому что хочу узнать. Потому что любознательный. Узнал что есть такая весчь «оченка времени работы алгоритма», узнал что она выглядит так. Теперь вникаю благодаря UT как ее осущетвлять.

ЗЫ: UT, а ты преподом чтоль работаешь? А то очень хорошо объясняешь.

Если, скажем, f(N) = O(N); g(x) = O(N^2), то ничего невозможно сказать про то, что больше, f(25) или g(25) — или любого другого конкретного N. Единственное, что можно сказать, это что если N увеличить в два раза, то f возрастет в 2 раза, а g возрастет в 4 раза.

«O большое» не подсчитывается. По определению,

O(x) = Cx

где C — произвольная константа, от x не зависящая. В контексте обсуждаемой проблемы — в нее идет время выполнения одной итерации. Разумеется, для разных алгоритмов она разная, поэтому сравнивать разные алгоритмы на этом основании нельзя.

Good Luck,

UT

ЗЫ А чей-то ты выкать начал? ;-)

Просто интересно. Учиться всегда интересно :).

ЗЫ: а ты случайно не преподом работаешь? А то очень ъхорошо объясняешь. Понятно и четко.

ЗЫ: а ты случайно не преподом работаешь? А то очень ъхорошо объясняешь. Понятно и четко.

Я ж говорил, я — профессор математики в одном американском университете, учу детей математике уже девять лет, начинал в Новосибирском Универе… Эх, какие у меня там студенты были, не то, что на этой помойке пяти континентов… Ну это уже офтоп пошел. Хотя да, разбираться всегда интересно.

Понятно теперь почему ты такой умный :) А не мог бы еще написать свои суждения на эту тему? Дополнить картину так сказать. Например как мне рассчитать быстродействие бинарного поиска? На мой взгляд оно где-то в районе О(N^3). Я правильно посчитал? (N-длина массива).

М-м-м… Что ты называешь бинарным поиском? Классический бинарный поиск — это Алгоритм 2 в моем примере (лев в пустыне). И он O(logN)…

Мда, как жалко, что я так редко заглядываю в раздел программирование :)))

Наверное потому, как врядли тут увижу интересное мне логическое программирование (ну или декларативное), поскольку вещи эти несколько иррациональны с точки зрения прикладного программирования..

Но тем не менее, оценка времени выполнения программы производится на двух этапах.

Алгоритмическом и программном. Хотя это уже упоминалось :)

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

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

Возьмём тот же самый поиск простых чисел. И для него рассмотрим несколько алгоритмов.

(почему-то так получилось, что на днях я наткнулся на одну из своих программок именно по поиску этих самых чисел, и в памяти много чего повылазило)

Исходно, ограничимся поиском всех простых чисел, вмещающихся в unsigned long, до 4\′294\′967\′295.

Алгоритм. Тупой до безобразия. Берём следующее число, тупо проверяем его делимость на все предыдущие и выводим его, если оно-таки простое. Сложность сего алгоритма для отдельного числа — O(N), для всего — O(N^2). Итого для случая поиска до 2^32-1 (4\′294\′967\′295) получаем где-то в районе «O»(2^64). А это, емнип, всего-то навсего «O»(18\′446\′744\′073\′709\′551\′616). Помрём, пока дождёмся :))

Упрощение 1. Нафига проглядывать все числа, если заведомо все чётные, кроме 2 — непростые? O(N) на число, и всё то же O(N^2) на весь алгоритм. Быстрее, конечно, чем без упрощения, но роли не играет.. Разиков эдав в 8 меньше..

Упрощение 2. Зачем пытаться делить на числа, бОльшие, чем корень_из(N)? О! вот тут качественный скачок — для одного числа — O(корень(N)), алгоритма — O(N^1.5). Итого будет порядка «O»(2^48) — а это уже получше..

Казалось бы, на этом и всё.. Однако, всё же есть и дальнейшее упрощение.

Упрощение 3. Нет необходимости делить на все нечётные числа, меньшие корня_из(N). Можно делить только на те, ято являются простыми. Так что там у нас со сложностью для одного отдельно взятого числа? O(число_простых_чисел_не_больших_корня_из(N)). Возникает вопрос, а сколько это? То, что это меньше, чем O(корень(N)), это так. Я бы сказал, что это o(log(N)), но доказательства строгого — нет. И общее будет o(N*log(N)). В том-то и дело, что «o», а не «O»!!