O(1)

Здравствуйте.
Прохожу один видеокурс и в нем дается понятие big O.
Правильно ли я понимаю, что при n = 10 время будет 10мс т.е. 1 операция в 1 мс и если n = 1000, время будет 1000 мс, т.е. так же 1 операция в 1 мс ? Т.е. по идее, изменений количества операций не произошло, как было 1 так и остается?
Т.е. само big O показывает изменение операций за промежуток времени, зависимое от входного числа данных? А не то, что 10*10 выполнится так же быстро как и 10⁶*10⁶? Или я не правильно понимаю.

Добавлено через 20 минут
Просто в курсе был пример с О(1):

0

Сообщение от Roy0Bannon Правильно ли я понимаю, что при n = 10 время будет 10мс т.е. 1 операция в 1 мс и если n = 1000, время будет 1000 мс

Неправильно.

O(1) означает, что алгоритм выполняется за фиксированное время.

Например выборка элемента массива. Неважно, 10 элементов в массиве или 1000 -- выборка будет производится за фиксированное время. Кстати, 10ms или 10ns -- зависит от процессора, поэтому когда речь идет о сложности алгоритма, конкретными величинами не оперируют.

Тот случай, который вы привели, называется O(n) -- то есть время выполнения алгоритма пропорционально количеству входных параметров. Например такая сложность будет у алгоритма получения суммы или произведения элементов массива.

Добавлено через 7 минут
Вот у этой ф-ции сложность будет уже O(n²)

0

Т.е умножение n*(n +1) /2 - это n*n/2 + n/2. Т.е. n*n - O(n), не O(1) как мне объясняют в курсе?

0

не не не, ваш второй пример с return n*(n + 1) / 2; -- это как раз O(1) -- потому что он выполняется за фиксированное время вне зависимости от входной величины.

1

Прежде чем понять O(), разберитесь с более простым понятием - число n. Что это за число? Размерность входных данных. Что же это?

1

Извиняюсь, я думал, что понял, но не понял в итоге. Т.е. получается для процессора вообще не важно какие цифры ему перемножать, например, 10² или 10⁶⁴ ? Время работы будет одно и то же? Я вот этого понять не могу.

0

Кстати, что хочу добавить... Очевидно, что два алгоритма с одинаковым Big-O вовсе не обязаны выполняться за одно и то же время.

Например, есть два алгоритма сортировки со сложностью O(n²) -- это вовсе не значит, что они одинаково эффективны.

0

Ну, это я понимаю, что n² - это условно, как бы. И можно 2n упростить до n. Это примерно как в геометрии 2 Пи и 4 Пи, одно и то же.

0

Сообщение от Roy0Bannon 102 или 1064

Если степень считать через умножения, то конечно время будет разным

одна операция в первом случае и 63 во втором -- налицо сложность O(n)

Но. Если в процессоре есть операция возведения в степень и время ее выполнения не зависит от степени, сложность будет O(1)

0

Хорошо. Можно ли тогда сказать, что О(1) как бы не существует, есть О(n), но на графике оно очень пологое?

0

Низзя...

https://miro.medium.com/max/82... 27-pyQ.png

0

Сообщение от Roy0Bannon Извиняюсь, я думал, что понял, но не понял в итоге. Т.е. получается для процессора вообще не важно какие цифры ему перемножать, например, 102 или 1064 ? Время работы будет одно и то же? Я вот этого понять не могу.

1. Определитесь, что является размерностью входных данных.
2. Одинаковая сложность не означает одинаковое время вычисления.

Например, есть задача вскопать (лопатой) конкретное поле. Сложность О(1). Размер поля фиксирован (заранее известен) и не влияет на сложность. Но это не значит, что Вы вскопаете сотку и гектар за одно и то же время.

Задача: перемножить столбиком 50 32-битных чисел. Слложность O(1).

Задача: перемножить столбиком n 32-битных чисел. Слложность O(n).

Задача: перемножить столбиком 50 m-битных чисел. Слложность O(m²).

Задача: перемножить столбиком n m-битных чисел. Слложность O(n * m²).

0

Вообще сложность O(1) при размерности входных данных n - это довольно нетривиальная ситуация. Представьте себе, n = 10000000000. Что значит О(1)? Это значит, что выход алгоритма не зависит от всех входных данных. Например: алгоритм сложения первого и последнего элемента массива размерности n.

Так понятно?

0

Сообщение от Mikhaylo Вообще сложность O(1) при размерности входных данных n - это довольно нетривиальная ситуация.

Тривиальная. Для большинства коллекций сложность некоторых операций О(1) - не зависит от размера коллекции.

0

Нетривиальность заключается в той хитрости, что такие алгоритмы не обращаются ко всем элементам, а только считывают значение нескольких элементов.

0

Если честно, я частично понял, но объяснить не могу. Я понимаю, что for loop внутри for loop'a будет на каждую операцию еще одна новая, и чем больше n входные данные, тем дольше будет обрабатываться такой код. А вот с О(1) я запутался совсем.
И еще проблема как определять по операциям в алгоритме, какому О он соответствует.
Может быть есть литература для начинающего и чтоб коротко и по делу, без лишней воды, ну и не в 1000 страниц. Очень хочу разобраться, хочу научиться писать нормальный код и думать какой алгоритм использовать, как лучше оптимизировать.
А часть ответов я вообще не понимаю тут.

0

Сообщение от Roy0Bannon А вот с О(1) я запутался совсем.

Давайте так. По правилам Big-O:
1. Сложность O(1) эквивалентна O(10) и даже O(100) и O(1 000 000).
2. Число n никогда не приравнивается 1, 10, 100 или 1 000 000, иначе бы вы O(n) смогли приравнять O(1).
3. Правильнее n приравнивать бесконечности. Но на практике вы можете осторожно приравнять любому числу, которое заведомо больше любого числа, характеризующего сложность в данной задаче.

Допустим, алгоритм выполняет сложение пяти случайных чисел из массива размера n. Происходит пятикратное обращение к массиву в цикле. Сложность O(5). Эквивалентно O(1).

Другой пример: алгоритм складывает все числа массива размерности n. Происходит n-кратное обращение к элементам массива в цикле. Сложность O(n). Приравнивать n=5 можете, но это некорректно, так как n правильно считать ооочень большим, т.е. бесконечностью в пределе. Если теперь в обеих задачах n=∞, то теперь понимаете разницу в сложности???

1

Начал курс на udemy смотреть. Более менее стал понимать. Потому как везде объяснялось big O, а что за ним стоит - нет. А тут и про бесконечность раскрыли и порядки, и остальное.

0

Сообщение от Roy0Bannon А тут и про бесконечность раскрыли и порядки, и остальное.

Теоретически, биг О определено для любой точки. Но в информатике нас интересует, как меняется время вычисления при увеличении размера входных данных - то есть, предел при стремлении эн к бесконечности.

0

Сообщение от vantfiles O(1) означает, что алгоритм выполняется за фиксированное время.

Неправда.

Сообщение от Shamil1 Теоретически, биг О определено для любой точки.

Насколько я себе представляю, О-большое может делаться только для предельной точки, чтоб можно было делать последовательность «стягивающихся» окрестностей. В это только .
Или я неправ?

0