Про асимптотическую оценку скорости алгоритмов

O(n^5) - в соответствии с математическим определением О большого.

Что такое по-вашему О?

f(x) = O(g(x)), если g(x) ограничивает сверху f(x) с точностью до постоянного множителя

что бы знать максимальную цену своим действиям

А, точно - в одну же сторону, но обычно и получается как и Θ. Оценку сверху проще сделать. (А эквивалентные точно не подойдут: вдруг колебания между двумя константами).

Почему используют О? А не тету или там эквивалентные функции

Прочитай первую встречную-поперечную книгу по оценке сложности алгоритмов - многие вопросы отпадут сами собой

Можно, но зачем?

Можно, но зачем?

Да не зачем. Верно ли это математически или нет? Просто для себя выяснить хочу.

и много тебе скажет выражение: у меня ва кармане меньше миллииона евро? а меньше ста? а меньше десяти?

математически: 0 < lim sup(f(x)/g(x)) < ~

supremum - минимальная из верхних границ.

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

инерция записи.

как уже отметили О большое как правило подразуемат тету ( т.е равенство ассимптот ,а не меньше_или_равно)

причина наверно в том что равенство с О большим эт ведь по чеснаку меньше или равно и когда приводят оценку указывают ниименшую сложность при которой выражение истино(т.е тету)

ум наверно на таких (как греческий и латынь в классических универах) и фильтруют ( ознакомся с 2 мя подходами ( образование это селекция способных VS образование это внедрение спектра навыков нужных народному хозяйству в сей момент)

в пределе у тебя излишне жёстко достаточно не ноль и не бесконечность (и быть числом . т.е не бесконечность и не ноль )

когда приводят оценку указывают ниименшую сложность при которой выражение истино(т.е тету)

вот он, ответ на мой вопрос :) Спасибо

точнее конечно же: f in O(g) => 0 <= lim sup(f(x)/g(x)) < ~

т.е запись с О однако как правило аргумент у О тета :)

если использовать \Theta(f(x)), то значит, что алгоритм будет всегда отрабатывать примерно в f(x) время. А при O(f(x)) может отработать и за меньшее, чем f(x).

Можно, но зачем?

Нельзя.

разве это не очевидно? представь две конторы. одна говорит, что построит мост за не больше чем за 1000 рублей. другая - не больше чем за 10000000…000 рублей. какая контора выиграет тендер?

хотя это конечно может и неудачная аналогия, но смысл тот же.

п.с. я только что офигел от капчи.

А мне кажется, или ответ кроется в вопросе:

Это можно оценить как O(n^2)... можно оценить это и как, например, O(n^5) - в соответствии с математическим определением О большого.

f(x) = O(g(x)), если g(x) ограничивает сверху f(x) с точностью до постоянного множителя

Т.е. O(const*n^2) -> O(n^2) как раз не тоже самое, что O(n^3*n^2). Первое - корректно, а второе противоречит определению, не так ли?