Что такое постоянные факторы и младший член в алгоритмах?

Ответ 1

младший член:

"Порядок" здесь относится к порядку величины.

Концепцию легко понять и объяснить при работе с очень простыми терминами, такими как x или x2. x имеет порядок величины 1, так как он может быть записан как x1, а x2 имеет порядок 2 - порядок величины равен мощности переменной в члене. Но вещи становятся немного более туманными (по крайней мере для меня), когда вы усложняете ситуацию, например, добавляя log. ^[1]

В несколько неофициальных терминах f(x) является более низким порядком, чем g(x), если f(x) < g(x) как x стремится к бесконечности.

Легко видеть, что f(n) = 6n является более низким порядком, чем g(n) = 6n*log2(n), просто подставив некоторое действительно большое значение для n (правильный подход - математически доказать его, но подстановка большого значения имеет тенденцию работать для простых термины).

условия - это вещи, разделенные символами плюс/минус.

Таким образом, младший член - это просто любой член, который имеет более низкий порядок, чем какой-либо другой член.

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

[1]: Я много разбираюсь в большом, но это было какое-то время (средняя школа?), так как я имел дело с основами порядка, поэтому извиняюсь, если бы я мог пропустить или забыть что-то относительно эта часть.

Постоянный фактор:

"Фактор" - это термин в умножении. Для 6n, 6 и n являются факторами.

Постоянный фактор - это просто все, что не зависит от входного параметра (s) (который в этом случае равен n).

Здесь, независимо от того, что мы делаем n, 6 всегда останется 6, поэтому он будет постоянным.

Ответ 2

Когда функция в big-O имеет несколько терминов, вы можете сохранить тот, который растет быстрее, потому что он "скрывает" других раньше или позже. И вы можете умножить на любую константу.

O(6.N.Lg(N) + 6.N) совпадает с O(6.N.Lg(N)) или O(N.Lg(N)) или O(0.01.N.Lg(N) + 42.sin(N) - 1.745 + 1/N)...

Доминирующий член всегда N.Log(N) (а базис логарифма не имеет значения).

Ответ 3

Обычно вам лучше задавать вопросы, связанные с курсами Coursera на форумах, где другие учащиеся могут помочь вам в тренировках, которые вы не можете понять сами.

Предположим, что у нас есть полиномиальная функция F (n) = 5n³ + 8n + 3, n³ имеет самый высокий показатель для нее, 5n³ - член высшего порядка многочлена. Все остальные термины, следовательно, являются членами младшего порядка.

Теперь почему они не актуальны. Ну, здесь определение большой записи O

T (n) = O (F (n)), если мы можем найти c и n0, например, для всех n >= n0 T (n) <= C.F(n)

• Можно доказать, что для любой полиномиальной функции F (N) = Cn.N ^ n + Cn-1.N ^ (n-1) +... + C0 F (N) = O (C.N ^ n) это доказательство приведено в видео.

• Можно также доказать, что для любых C и K, C.N ^ K = O (N ^ K) (просто возьмем c = C)

• Наконец, мы можем доказать, что если F (n) = O (G (n)) и G (n) = O (K (n)), то F (n) = O (K (n)), это свойство называется транзитивностью.

• Затем заключаем, что каждая функция T (n) = O (F (n)), где F - многочлен, также O (n ^ k), где k - наивысший показатель многочлена F.

Для простоты мы уменьшаем F до самого высокого порядка и оставляем постоянный множитель при сохранении математической корректности.