Re: Составление школьного расписания

From

pav ()

To

All ()

Date

2000-02-27T13:37:23Z

Area

RU.ALGORITHMS

From: "pav" <pav@intis.iom.tsc.ru>

Hi, All.
Boris Rudakov <Boris.Rudakov@p4.f9.n5054.z2.fidonet.org> сообщил в новостях
следующее:951478909@p4.f9.n5054.z2.ftn...

>  AB> Я согласен потратить месяц
> Ты шутишь - за месяц можно отрендерить чуть ли не половину графики для
крутого
> голливудского фильма, а там вычислительные задачки не в пример серьезней
:)

Господа, можно я объясню всю несостоятельность данного аргумента? Спасибо.

Есть такая штука, довольно-таки условная, - трудоемкость алгоритма. Те, кто
знает о чем я, просьба пропустить это (гневное :-) письмо. Есть, опять же
довольно-таки условная мера - производительность (вычислителя). Объяснять
смысл этих величин в данной эхе мне представляется глупым (надежда умирает
последней). А вот о их взаимосвязи я и хотел бы поговорить, дабы впредь
воздерживаться от таких аргументов. Представим себе два вычислителя
10.000.000 оп/сек и 20.000.000 оп/сек (я утрирую). Второй - "в два раза
быстрее" (левый хвост -длиннее :-). Возьмем линейный алгоритм (читай
алгоритм с линейной трудоемкостью, ~O(x))- к примеру цифровая
сортировка. ->Все пока подтверждается. -> Действительно, время затраченное
на сортировку равновеликих массивов на втором вычислителе в два раза меньше.
Или другими словами за равное время второй вычислитель отсортирует массив в
два раза больший чем первый вычислитель. Возьмем квадратичный алгоритм
(~O(x^2)). Продолжать? Надеюсь, уже совсем все поняли что второй вычислитель
не "в два раза быстрее". А что самое печальное, это еще ох, какой не предел
трудоемкости. И здесь я не иронизирую, мне действительно печально. Так что,
к примеру, если алгоритм ~O(x^x) со входом на 5 элементов, можно было
худо-бедно использовать на "троечке" (я утрирую), то со "всего лишь в два
раза большим" входом - я крупно сомневаюсь, потянут ли его современные
суперкомпьютеры. Надеюсь, что мое письмо не пропадет даром.

    Ищущие - да обрящутЪ.
    Обучающиеся - да постигнутЪ.

С уважением,
    Милованцев Павел.


--- ifmail v.2.15dev4
 * Origin: Tomsk State University (2:5020/400)