Они могут быть хуже на какой-то n-ой итерации, а на n+1 улучшать ситуацию и становиться выгоднее. Но это всё запары, чаще всего для NP-полных задач используют жадные алгоритмы, если не требуется находить самое оптимальное решение. Диванный КЭП.
Побуду незванным кэпом!
Это оценки вычислительной сложности алгоритмов относительно размера обрабатываемых данных. O(1) дает ответ моментально. O(n!)... Бля, если мне даже записывать его стрёмно...
>O(1) дает ответ моментально.
Ты плохой кэп. O(1) дает ответ за константное время, не зависящее от размера входных данных, а не моментально. Если программа будет давать ответ за 1 год для любого n - это тоже будет O(1).
Естественно, предметные знания это - преамбула. Далее должна включаться логика. И только так мы можем продвигаться в освоении науки. А хвастовство - это для менеджеров.
Где можно почитать про большое О на конкретных примерах? Куча раз про него слышал и даже имею небольшое представление но всё же хочу разобраться в этом.
Допустим алгоритм, который O(n) 5 элементов обрабатывает 10 секунд. Значит 10 элементов он будет обрабатывать 20 секунд.
O(n^2) обрабатывает 5 элементов 10 секунд, а 10 элементов уже 40 секунд.
Но это не точно, я не эксперт
А че тут разбираться? Апроксимирующая функция количества вычислений(циклов, как правило) от размера задачи. Как правило, в той же вики, на любом алгоритме написана его вычислительная сложность.
Вроде даже был какой-то оптимизационный алгоритм с полиномиальной сложностью, который на практических задачах выполнялся дольше, чем экспоненциальный перебор.
уравнений Янга — Миллса в общем случае является одной из семи математических «Проблем тысячелетия», за решение которой Математический институт Клэя присудит премию в 1 миллион долларов США. Так что да формула это просто.
Кто-н знает, почему фразу "oh you are approaching me" в мемах приписывают Жотаро (который справа), когда ее произносил Дио (который слева размашисто шагает)? Это потому что они само аниме не смотрели, а на стопкадре Жотаро якобы стоит, а Дио шагает, и поэтому у них сложилось впечатление, что эту фразу говорил именно Жотаро?
Это оценки вычислительной сложности алгоритмов относительно размера обрабатываемых данных. O(1) дает ответ моментально. O(n!)... Бля, если мне даже записывать его стрёмно...
Ты плохой кэп. O(1) дает ответ за константное время, не зависящее от размера входных данных, а не моментально. Если программа будет давать ответ за 1 год для любого n - это тоже будет O(1).
Допустим алгоритм, который O(n) 5 элементов обрабатывает 10 секунд. Значит 10 элементов он будет обрабатывать 20 секунд.
O(n^2) обрабатывает 5 элементов 10 секунд, а 10 элементов уже 40 секунд.
Но это не точно, я не эксперт
Книжка просто написана, да еще и с картиночками)
http://cdn01.ru/files/users/images/f8/4e/f84ec31d0d97d8dfaba170a278334de8.png
http://femto.com.ua/articles/part_2/p1/5040-48.jpg