Искуственный Интеллект

 
1 2 3 4
+
-
edit
 

Mishka

модератор
★★☆
ab>Правда дальше все не так гладко. Вот например еще цитатка - красота символа О в том, что он скрывает несущественные детали, и позволяет сконцентрироваться на существенных особенностях поведения. Ну конечно разве произвольная константа это важно, подумаешь на пару порядков больше или меньше. Правильнее было бы сказать, не - скрывает несущественные детали, а - ничего о (весьма существенных) деталях сказать не может, а дает только крайне неточныю качественную оценку, это было бы ближе к истине.

Давайте посмотрим что говорит нам О для методов сортировки. Возьмем пузырек и сортировку кучей (heap sort). Первая O(n2), вторая - O( n*log2(N) ). Никаких констант. Что из этого видно? А то, что для малых наборов пузырек работает быстрее (хотя бы для N=1). Но... имеется точка, где куча будет экономней - всегда. И это преимущество может расти. И это не зависит от констант. Что ж, теперь, если надо точно найти границу, где этот скачок происходит, то надо смотреть на конкретные формулы и решать систему уравнений. Какой вывод из этого - а такой, если применять сортировку там, где наборы велики, то пузырек надо выбрасывать - без рассмотрения констант. Это чисто математический анализ. Для конкретного применения этого О может не хватить - вот здесь я и говорю, что надо обосновать модель. Нельзя вот так вот взять и сказать, что куча всегда лучше. Нельзя бездумно переносить метод на любые условия.
 
Я скорее о том, что красивые оценки остаточных членов полученные для многих полезных разложений/приближений (в виде О или о) для практических вычислений увы бесполезны. Вот и приходится при суммировании эмпирически ориентироваться на изменение поведения последовательности частичных сумм или похожих вещей, в лбщем на всякую эмпирику.

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

Оба примера иллюстрируют, что не все так хорошо с теорией (даже довольно простых вещей), как хотелось бы.
 
+
-
edit
 

Mishka

модератор
★★☆
ab>Я скорее о том, что красивые оценки остаточных членов полученные для многих полезных разложений/приближений (в виде О или о) для практических вычислений увы бесполезны. Вот и приходится при суммировании эмпирически ориентироваться на изменение поведения последовательности частичных сумм или похожих вещей, в лбщем на всякую эмпирику.

А для этого он и не предназначен :) Оценка поведения немного из другой оперы - это скажем как ускорение - без знания начальной скорости не позволяет сказать какой предмет долетит из точки А в точку Б, но динамику изменения показывает. Только ускорение потом можно еще использовать для вычислений, а О нельзя.

ab>В примере с сортировками та же проблема – что такое "большой набор" для конкретной задачи определить с помощью этих соотношений нельзя. Практически опять же проще сделать несколько прогонов двух методов и сравнить результаты.

А О гарантирует, что какие бы константы большие не были, всегда N2 обгонит N*log2(N). Это как теорема существования.

ab>Оба примера иллюстрируют, что не все так хорошо с теорией (даже довольно простых вещей), как хотелось бы.

Я как раз думаю, что все наоборот - теория показывает, что все живет по закону, не зависящему от желания. О есть одна сторона и никто не говорит, что только ею и надо ограничиться. Если надо конкретные цифры, то надо другие методы/теории использовать.
 
1 2 3 4

в начало страницы | новое
 
Поиск
Настройки
Твиттер сайта
Статистика
Рейтинг@Mail.ru