Могу ли я упростить условия при вычислении Big O?

Я хочу вычислить время выполнения следующей функции

T (n) = (1 + 2 + 3 + 4 + 5 + ... + n) /n

Вначале мне это не показалось трудным, потому что его можно легко решить, преобразуя формулу

T (n) = (n (n-1) /2) /n = (n ^ 2-n) /n = n-1, что приводит к O (n).

Подумав об этой функции, я боролся. Я не уверен, разрешено ли мне сокращать n, потому что я не знаю кода, стоящего за этой функцией.

Например, это может быть что-то вроде

method foo()
{
          methodWhichTakesNCubeAmountOfTime(); //Build sum, O(n^2)
          methodWhichTakesNAmountOfTimeAndCantBeSimplified(); //O(n)
}

Для этого метода я получаю n кубов в качестве среды выполнения.

  

O (n ^ 2) + O (n) = O (n ^ 2)

Я знаю, что этот метод не распространяется на исходный термин, но я надеюсь, что вы получите то, что я имел в виду: Разделенный на n может быть полностью дифференцированной функцией (которая имеет случайную сложность n), и поэтому я не могу ограничить другие n с ним.

Так что я смущен. Мне разрешено преобразовывать термины обычно во время вычисления Big O или некоторые математические правила не применяются здесь?

Спасибо.

1 голос | спросил BudBrot 20 Jpm1000000pmSat, 20 Jan 2018 16:48:36 +030018 2018, 16:48:36

1 ответ


7

Не только вы можете, но и в самом определении O-сложности.

O-сложность на самом деле не так проста, как это понимают большинство программистов-непрофессионалов.

Проще говоря, O определяется асимптотически. Это означает, что вы пытаетесь понять, как будет работать алгоритм, если n приближается к бесконечности. И в большинстве случаев один из них доминирует над расчетом. Ваш пример

O(n^2) + O(n) = O(n^2)

- хорошее представление этого. Хотя для небольших n, код O(n) влияют на время, для n приближается к бесконечности, O(n) становится пренебрежимо малым по сравнению с O(n^2). Так что просто игнорировать его.

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

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

Например, у вас могут быть два алгоритма. Один O(n^2) и второй O(1000*n). Первый, очевидно, будет быстрее для n меньше 1000. Но поскольку константы отбрасываются, чтобы сложность была «правильной», тогда вторая должны быть действительно записаны как O(n).

ответил Euphoric 20 Jpm1000000pmSat, 20 Jan 2018 17:38:58 +030018 2018, 17:38:58

Похожие вопросы

Популярные теги

security × 330linux × 316macos × 2827 × 268performance × 244command-line × 241sql-server × 235joomla-3.x × 222java × 189c++ × 186windows × 180cisco × 168bash × 158c# × 142gmail × 139arduino-uno × 139javascript × 134ssh × 133seo × 132mysql × 132