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

O(N^2*logN)

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

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

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

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

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

http://en.wikipedia.org/wiki/Computational_complexity_theory

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

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

http://www.cprogramming.com/tutorial/computersciencetheory/algorithmicefficiency3.html

Good Luck,

UT

И здесь:

http://users.forthnet.gr/ath/kimon/CC/CCC1b.htm

Good Luck,

UT

Сенькс.

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

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

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

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

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

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

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

Good Luck,

UT

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

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

Ищем число 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 большое» не подсчитывается. По определению,

O(x) = Cx

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

Good Luck,

UT

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

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

Если, скажем, 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, а ты преподом чтоль работаешь? А то очень хорошо объясняешь.

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

Если, скажем, 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

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

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

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

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

это как?

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

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

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

Good Luck,

UT

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

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

http://www.tbray.org/ongoing/When/200x/2003/03/22/Binary

Good Luck,

UT

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

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

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

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

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

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

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

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

Исходно, ограничимся поиском всех простых чисел, вмещающихся в 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»!!

А теперь вопрос:

А как оценить o(N*logN)? Что-то я не очень понял на сколько от этого станет легче?

ммм… я тут немного глюкнул, когда писал — o(N*log(N)) — это нижняя граница, т.е. меньше этого — быть не может.

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

Количество простых чисел меньших или равных x можно считать равным x/log(x)

http://www.utm.edu/research/primes/howmany.shtml

Стало быть, если твоя задача стоит как Найти все простые числа меньше N, и ты решаешь ее путем перебора простое-непростое, то у тебя сразу выскакивает не меньше O(N) операций. Далее, деля на каждое уже найденное простое, ты получаешь еще N/log(N) операций, всего — O(N^2/log(N)). Поскольку log(N) растет медленнее, чем любая степень N, твой алгоритм асимптотичен O(N^2), т.е. почти никакого выигрыша по сравнению с Тупым алгоритмом НЕТ!

Корень зла — в переборе. Решето Эрастофена тем и хорошо, что оно не заставляет перебирать все числа…

Good Luck,

UT

O(N^2) ?

Упрощение 2 дало для числа O(N^0.5), для всех — O(N^1.5), что меньше даже O(N^2/log(N)), которое, действительно, ассимптотично O(N^2).

Упрощение 3 даёт для одного числа, судя по ссылке, даст O(N^0.5/log(N)), для всех — ….ммм… ответ дам, как только до формул доберусь, с ходу не получается ответить ;) Но порядок, тем не менее, будет не больше O(N^1.5/log(N)), что, однако, не так уж и сильно отличается (ассимптоматично) от O(N^1.5)…. (но при поиске до 2^32, тем не менее, в разы меньше).

В чистом виде решето Эратосфена на компьютере эффективно не реализуешь, приходится так или иначе обходиться перебором. (при поиске до 2^32 минимум памяти, используя бинарные массивы, 2^32 (бит)/8 (байт/бит) = 2^29 (байт) = 512 Мб. Меньше, чем я использую в своей программе, 1.04 Гб, но накладные расходы на время выполнения у меня меньше.)

Ладно, уговорил. Действительно, можно проверять делимость на простые числа меньше или равные корня из x.

А про решето — печему его трудно алгоритмизировать? Можно поиграться на досуге…

Good Luck,

UT

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

В чистом виде решето Эратосфена на компьютере эффективно не реализуешь.

Точнее только после того, как мне расскажут, как эффективно реализовать «вычёркиваем все числа, кратные данному».