Как измеряется О большая?

Как я понял, это скорость работы алгоритма.

Но как она измеряется? Количество итераций цикла? Количество сравнений?

Я не понимаю, как считается n.

Ответ, который ты мог найти в гугле за 15 секунд, но решил потратить 15 минут и получить его на форуме

Измеряется в абстрактных теоретических итерациях(тактах).

условная единица времени

>О-большое

>Измеряется

Боже, за что?! Просто прочти Википедию, там же по-русски написано.

Legatus Legionis сказал(а):↑

>О-большое

>Измеряется

Боже, за что?! Просто прочти Википедию, там же по-русски написано.

Нажмите, чтобы раскрыть...

Не нашел, подскажи пожалуйста

капец ты часто бухаешь конечно

Пирожок с капустой сказал(а):↑

Ответ, который ты мог найти в гугле за 15 секунд, но решил потратить 15 минут и получить его на форуме

Измеряется в абстрактных теоретических итерациях(тактах).

Нажмите, чтобы раскрыть...

Т.е. если у меня будет одна итерация цикла, но в ней 100 команд и 1 команда, это будет одна скорость?

Meepka сказал(а):↑

капец ты часто бухаешь конечно

Нажмите, чтобы раскрыть...

Если нечего писать, то не надо флудить

Я спрашиваю людей которые хоть немного в теме

y6ejushe сказал(а):↑

Т.е. если у меня будет одна итерация цикла, но в ней 100 команд и 1 команда, это будет одна скорость?

Нажмите, чтобы раскрыть...

В O нотации фактическое кол-во шагов не важно, важно что алгоритм выполняется за время, близкое к какой-то формуле(константное, линейное, логарифмическое, квадратное), т.е. если фактически, скажем цикл будет сложностью n log n +100*n или n log n +n (для 1 команды) то в O-нотации хвост отбрасывается, и останется сложность n log n. Прибавляя константу, ты просто видоизменяешь функцию, но ее суть остается той же, на деле проще отбросить лишнее и прикинуть рост функции, это делается для оценки сложности, а не для подсчета количества команд

alcoholtrash сказал(а):↑

В O нотации фактическое кол-во шагов не важно, важно что алгоритм выполняется за время, близкое к какой-то формуле(константное, линейное, логарифмическое, квадратное), т.е. если фактически, скажем цикл будет сложностью n log n +100*n или n log n +n (для 1 команды) то в O-нотации хвост отбрасывается, и останется сложность n log n. Прибавляя константу, ты просто видоизменяешь функцию, но ее суть остается той же, на деле проще отбросить лишнее и прикинуть рост функции, это делается для оценки сложности, а не для подсчета количества команд

Нажмите, чтобы раскрыть...

Короче, главное количество повторений.

y6ejushe сказал(а):↑

Если нечего писать, то не надо флудить

Я спрашиваю людей которые хоть немного в теме

Нажмите, чтобы раскрыть...

хороший совет, советую прислушаться к нему

y6ejushe сказал(а):↑

Т.е. если у меня будет одна итерация цикла, но в ней 100 команд и 1 команда, это будет одна скорость?

Нажмите, чтобы раскрыть...

f лежит в классе O(g) в точке x_0 (или как это записывают f = O(g), x -> x_0)

если существует константа C, такая что существует окрестность вокруг x_0, такая что все x в этой окрестности удовлетворяют f(x) < C g(x)

в computer science практически всегда речь идёт о x -> +∞, поэтому это опускают

окрестностью становятся лучи вида [ t; +∞ )

то есть начиная с некоторого t для всех x должно выполнятся соотношение с константой

дальше возникает арифметика своеобразная (включение классов)

например ты всегда можешь повысить класс

O(n) = O(n^2) = O(n^3) ... = O(2^n) = O(3^n) ... = O(n ^ n) ...

но обратное неверно:

O(n^2) != O(n)

их можно умножать

O(f) * O(g) = O(f * g)

нельзя делить

O(f) / O(g) != O(f / g)

можно складывать, но смысла в этом мало

потому что всё равно оно эквивалентно максимуму из двух

O(f) + O(g) = O(max f g)

вычитание работает как сложение

O(f) - O(g) = O(max f g)

можно делить на конкретные функции

например this is perfectly legal

O(n) / n = O(1)

можно брать функции

sin(O(f)) = O(1)

можно брать от этой ерунды суммы

sum O(i^2) for i in 1 ... n] = O(n^3)

в общем всё что пожелаешь

главное руководствоваться здравым смыслом и определением