Big O, как вы рассчитываете / приближаете это?

Question

Большинство людей со степенью в CS наверняка знают, что означает Big O . Это помогает нам измерить, насколько (не) эффективен алгоритм на самом деле, и если вы знаете, в , в какой категории находится проблема, которую вы пытаетесь решить, в , вы можете выяснить, все еще возможно ли выжать этот маленький дополнительная производительность. ¹

Но мне любопытно, как вы рассчитываете или приближаете сложность ваших алгоритмов?

¹ _{но, как говорится, не переусердствуйте, преждевременная оптимизация - корень всего зла , и оптимизация без уважительной причины должна заслужить это имя как хорошо.}

Answer 1

Я не знаю, как программно решить эту проблему, но первое, что делают люди, это то, что мы выбираем алгоритм для определенных шаблонов по количеству выполненных операций, скажем, 4n ^ 2 + 2n + 1, у нас есть 2 правила:

1. Если у нас есть сумма терминов, то термин с наибольшим темпом роста сохраняется, а другие термины опускаются.
   
2. Если мы имеем произведение нескольких факторов, постоянные факторы опускаются.

Если мы упростим f (x), где f (x) - формула для числа выполненных операций (4n ^ 2 + 2n + 1, объясненное выше), мы получим значение big-O [O (n ^ 2 ) в этом случае]. Но это должно было бы учитывать интерполяцию Лагранжа в программе, что может быть трудно реализовать. А что если реальное значение big-O было O (2 ^ n), и у нас могло бы быть что-то вроде O (x ^ n), поэтому этот алгоритм, вероятно, не был бы программируемым. Но если кто-то докажет, что я неправ, дайте мне код. , , .

Answer 2

Для кода A внешний цикл будет выполняться в течение n+1 раз, время '1' означает процесс, который проверяет, соответствует ли я требованию. И внутренний цикл выполняется n раз, n-2 раз .... Таким образом, 0+2+..+(n-2)+n= (0+n)(n+1)/2= O(n²).

Для кода B, хотя внутренний цикл не вступает и не выполняет foo (), внутренний цикл будет выполняться n раз в зависимости от времени выполнения внешнего цикла, которое равно O (n)

Answer 3

Я хотел бы объяснить Big-O в несколько ином аспекте.

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

ИМХО в формулах big-O лучше не использовать более сложные уравнения (вы можете просто придерживаться приведенных на следующем графике.) Однако вы все равно можете использовать другую более точную формулу (например, 3 ^ n, n ^ 3). , ...) но иногда это может вводить в заблуждение! Так что лучше держать как можно проще.

Я хотел бы еще раз подчеркнуть, что здесь мы не хотим получить точную формулу для нашего алгоритма. Мы только хотим показать, как он растет, когда входы растут, и сравнить в этом смысле с другими алгоритмами. В противном случае вам лучше использовать другие методы, такие как тестирование.