сложность прохождения от начала до конца и обратно через вектор

Question

Я пытаюсь ознакомиться с оценкой сложности алгоритмов. В целом, я думаю, что это хорошая / элегантная практика, но в конкретном случае она мне нужна, чтобы выразить временную сложность моего кода C ++.

У меня есть небольшое сомнение. Предположим, у меня есть алгоритм, который просто читает данные от начала std::vector до конца; затем он делает то же самое, начиная с конца до начала (как и 2 цикла для индексов «От 0 до N», а затем «От N до 0»).

• Я сказал себе, что сложность этого материала - O (2N): это правильно?
• Как только я достиг начала, предположим, что я хочу снова начать читать все данные от начала до конца (проходя в общей сложности 3 раза по вектору): сложность O (3N)?

Возможно, это глупое сомнение, но я бы все равно хотел, чтобы кто-то высказал свое мнение о моем процессе мышления.

Answer 1

Обозначение Big-O просто означает:

f (n) = O (g (n)) тогда и только тогда, когда f (n) / g(n) не увеличивается до бесконечности, так как n увеличивается

Что вам нужно сделать, это подсчитать количество операций, которые вы выполняете, то есть f (n) , а затем найдите функцию g (n) , которая увеличивается по меньшей мере так же быстро, как f .

В вашем примере перехода в одну сторону и обратно количество операций равно f (n) = 2n , поскольку каждый элемент читается дважды, поэтому вы можете выбрать g(n) = n .Поскольку f (n) / g (n) = 2n / n = 2 , очевидно, не растет до бесконечности (это константа), у вас есть алгоритм O (n) .

Это также алгоритм O (2n) , конечно: свойство «расти до бесконечности» не меняется, когда вы умножаете g (n) напостоянная, любая O (g (n)) также по определению является алгоритмом O (C g (n)) для любой постоянной C .

И это также алгоритм O (n²) , потому что 2n / n² = 2 / n уменьшается до нуля.Нотация Big-O обеспечивает только верхнюю границу сложности.

Answer 2

O (N), O (2N) и O (3N) эквивалентны.Умножение постоянного коэффициента на функцию внутри O () не изменит ее сложности на «линейную».

Однако верно, что при каждом сканировании будет выполнено N операций чтениянаправление, т. е. будет выполняться чтение 2N ∈ O (N) при сканировании от начала и до конца, а чтение 3N ∈ O (N) при сканировании от начала до конца, от начала до конца.

Answer 3

Важно получить рабочее представление для обозначения Big-O.Я попытаюсь передать это ...

Как вы говорите, ваш алгоритм интуитивно "O (2N)", но представьте, что кто-то еще пишет алгоритм, который повторяется только один раз (следовательно, явно O (N))но тратит в два раза больше времени на обработку каждого узла или в сто раз больше.Вы можете видеть, что O (2N) только очень слабо наводит на мысль о чем-то более медленном, чем алгоритм O (N): не зная, что это за операции, O (N) может быть быстрее всего, скажем, в 50,1% случаев.

Big-O становится значимым только тогда, когда N становится огромным: если ваши операции изменяются по длине, скажем, 1000: 1, тогда разница между алгоритмами O (N) и O (NlogN) становится доминирующей только тогда, когда N превышает 1000 в квадрате (т.е.+1000000).Итак, нотация Big-O предназначена для рассуждения о стоимости операций на больших наборах, в которых линейные факторы, такие как 2x или 10x, просто не считаются релевантными и игнорируются.