Асимптотические обозначения.
Время выполнения программы описывается некоторой функцией Для описания асимптотических оценок имеется система нотаций: § Говорят, что f(n)= O (g(n)), если существует такая константа c>0 и такое число n0, что выполняется условие 0≤f(n)≤c*g(n) для всех n≥n0. Более формально: O (g(n)) используется для указания функций, которые не более чем в постоянное число раз не превосходятg(n), этот вариант используется для описания оценок сверху (в смысле «не хуже чем»). § Говорят, что f(n)= W (g(n)), если существует такая константа c>0 и такое число n0, что выполняется условие 0≤c*g(n)≤f(n) для всех n≥n0. Более формально: W (g(n)) используется для указания функций, которые не менее чем в постоянное число раз превосходят g(n), этот вариант необходим для описания оценок снизу (в смысле «не лучше чем»). Следующее определение объединяет предыдущие случаи: § Говорят, что f(n)= Q (g(n)), если найдутся такие константы c1,c2>0 и такое число n0, что для всех n≥n0 выполняется условие 0≤c1*g(n)≤f(n)≤c2*g(n). В этом случае, говорят - функция g(n) является асимптотически точной оценкой для f(n).
Q (g(n)) используется для указания функций того же порядка, что и g(n), этот вариант используется для описания асимптотически точных оценок. Асимптотические сравнения обладают некоторыми свойствами отношений действительных чисел: Транзитивность Из f(n)= Q (g(n)) и g(n)= Q (h(n)) следует f(n)= Q (h(n)). Из f(n)=O(g(n)) и g(n)= O (h(n)) следует f(n)= O (h(n)). Из f(n) = W (g(n)) и g(n) = W (h(n)) следует f(n) = W (h(n)). Рефликсивность Из f(n)= Q (f(n)). Из f(n)= O (f(n)). Из f(n) = W (f(n)). Симметричность f(n)= Q (g(n)) справедливо тогда и только тогда, когда g(n)= Q (f(n)). Перестановочная симметрия f(n)=O(g(n)) справедливо тогда и только тогда, когда g(n)= W (f(n)) Как ведут себя значения приведенных выше функций в зависимости от размера решаемых задач демонстрирует таблица В зависимости от асимптотической функции времени решения может быть рассчитан размер задач, решаемых с такой скоростью. Границы размера задач, определяемых скоростью роста сложности Несмотря на то, что основное внимание здесь уделяется порядку роста величин, надо понимать, что большой порядок роста сложности алгоритма может иметь меньшую мультипликативную постоянную, чем малый порядок роста сложности другого алгоритма. В таком случае алгоритм с быстро растущей сложностью может оказаться предпочтительнее для задач с малым размером — возможно, даже для всех задач, которые нас интересуют.Например, предположим, что временные сложности алгоритмов
Читайте также: Воспользуйтесь поиском по сайту: ![]() ©2015 - 2025 megalektsii.ru Все авторские права принадлежат авторам лекционных материалов. Обратная связь с нами...
|