В следующем видео описываются некоторые проблемы асимптотического анализа: https://class.coursera.org/algo-004/lecture/169
Но я не могу понять, что такое "младший член" и "постоянный фактор"? (это на 4-й минуте видео).
Сортировка слияния 6n*log2(n)+6n. Почему 6n - младший член в случае, упомянутом в видео, а 6 - constant factor? У этих терминов есть конкретное определение?
младший член:
"Порядок" здесь относится к порядку величины.
Концепцию легко понять и объяснить при работе с очень простыми терминами, такими как 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, поэтому он будет постоянным.
Когда функция в 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) (а базис логарифма не имеет значения).
Обычно вам лучше задавать вопросы, связанные с курсами 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 до самого высокого порядка и оставляем постоянный множитель при сохранении математической корректности.