Студопедия
Случайная страница | ТОМ-1 | ТОМ-2 | ТОМ-3
АрхитектураБиологияГеографияДругоеИностранные языки
ИнформатикаИсторияКультураЛитератураМатематика
МедицинаМеханикаОбразованиеОхрана трудаПедагогика
ПолитикаПравоПрограммированиеПсихологияРелигия
СоциологияСпортСтроительствоФизикаФилософия
ФинансыХимияЭкологияЭкономикаЭлектроника

Асимптотические методы. Асимптотически точная оценка. Оценки сверху и снизу.

Последовательности. Производящие функции. Операции над производящими функциями. | Линейные рекуррентные соотношения с постоянными коэффициентами. Общий метод решения рекуррентных соотношений. | Основная теорема о рекуррентных соотношениях. | Эйлеровы циклы. Теор. о сущ. эйлерова цикла. Уникурсальные графы. Гамильтоновы циклы. |


Читайте также:
  1. II. Показатели продовольственной безопасности Российской Федерации и критерии их оценки
  2. II. Показатели продовольственной безопасности Российской Федерации и критерии их оценки
  3. IV зона восточная зона тектонических структур.
  4. IV. Критерии оценки реализации Программы .
  5. Swot-анализ как метод оценки конкурентных позиций и обеспечения конкурентных преимуществ
  6. АККРЕДИТАЦИЯ КАК ОДНА ИЗ ФОРМ ОЦЕНКИ КАЧЕСТВА ВЫСШЕГО ОБРАЗОВАНИЯ
  7. Алгоритм оценки характера местности для участков маршрута .

Опр. 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-и красках.| Множества.

mybiblioteka.su - 2015-2024 год. (0.008 сек.)