Еще раз о вычислительной сложности алгоритмов



Posted by Анатолий Анимица (194.177.32.67) on February 04, 2001 at 13:07:28:

In Reply to: Теория... FIFO posted by Валентин, Донецк on February 03, 2001 at 16:07:05:

Пример, который привел Валентин, еще раз свидетельствует о необходимости тщательно оценивать сложность алгоритма. В частности, если у вас в алгоритме есть цикл по массиву длиной N и внутри него еще один цикл по другому массиву длиной M (N, если это один и тот же массив), то при равных (в данном случае "равных" - это отличающихся на константу, например, 1 или 1000 - все равно) затратах на вычисление одного шага цикла вы получите принципиально не решаемый алгоритм при размере N и M, например, 1000.
Потому что 10*10 шагов - это 100, 100*100 шагов - это 10000, а 1000*1000 шагов - это миллион.
Теперь представьте себе, что вся эта куча шагов должна вычисляться в каждой из опять же N операций. Мы получим N*N*N - и вот он, миллиард. Никаких гигагерц не хватит. Поэтому я еще раз призываю - овладевайте знаниями! Не такое уж это сложное дело, не считайте за труд поставить себя на место алгоритма и вспомните Александра Галича: ".. говорит он ей - а ну, помножь-ка мне, девятьсот на девятьсот с ноль сотою, а потом сидит, качает ножкою - сам сачкует, а она работает". И так далее, очень хорошая песня про автоматизцию тоже.

Я временно снес 2001R - идут существенные переделки, и в этом ключе тоже. Но те, кто успел скачать, могут посмотреть сведение квадратичного алгоритма к строго линейному в форме sklad.rpt.
И еще. Где-то у нас лежит моя старая "домашняя бухгалтерия" - в ней есть пример алгоритма NlogN, вычисляющий простые числа в операциях из файла-коэффициента. Там тоже все очень прозрачно написано.

А Вы, Валентин, можете обратиться со своей проблемой прямо ко мне - обсудим пути ее решения. С уважением
AAA





Пpишедшие ответы: