Читайте также:
|
|
Опр. 1: Пусть имеются ф-и f(n) и g(n). Пусть они неотриц. при дост. больших n. Говорят, что f(n)=θ(g(n)) {f(n) есть θ(g(n))}, если , для кот. можно подобрать такое значение n0, что выполняется: 0≤с1g(n)≤f(n)≤c2g(n). . Точная асимптотическая оценка.
Опр. 2: Пусть имеются ф-и f(n) и g(n). Пусть они неотриц. при дост. больших n. Говорят, что f(n)=О(g(n)) {f(n) есть О(g(n))}, если , что выполн.: 0≤f(n)≤cg(n). Асимптотич. оценка сверху.
Говорят, что f(n)=Ω(g(n)), если , что выполн.: 0≤cg(n)≤f(n). Асимпт. оценка снизу
Опр. 3: Пусть имеются ф-и f(n) и g(n). Пусть они неотриц. при дост. больших n. Говорят, что f(n)=o(g(n), если , что 0≤f(n)≤εg(n). Уточнённая асимпт. оценка сверху.
Говорят, что f(n)=ω(g(n)), если , что 0≤εg(n) ≤f(n). Уточн. асимпт. оц. снизу.
Дата добавления: 2015-07-20; просмотров: 125 | Нарушение авторских прав
<== предыдущая страница | | | следующая страница ==> |
Раскрашивание графа. Хроматическое число графа. Теор. о 5-и красках. | | | Множества. |