На главную

2. Пригодится ли глубокое знание математики или можно обойтись элементарной, поскольку процессор использует только арифметические и логические операции?

 

Ответ простой  - пригодится, для того, чтобы не писать лишнего кода или не греть процессор понапрасну.

Например, несложно создать программу возведение в степень, используя только операцию  сложения, труднее будет потом ее остановить.

Другой случай. Для чисел, длиной в n знаков,  школьный алгоритм умножения поглощает O(n2) вычислительных ресурсов. Однако, применяя метод быстрого преобразования Фурье, можно добиться оценки O(nlogn).

А куда делась одна степень у n ? Ведь, O(logn) по сути, мало значит.

В бухгалтерии природы  ничто не пропадает бесследно, а если более точно, то действует закон сохранения – если в одном месте украли, то в другом месте добавят.

Ответ физика может быть таким – школьный алгоритм не совершенен, мы просто увеличиваем хаос Вселенной. Но это не так. Кто писал программы умножения маленьких или больших чисел отлично знает, что для малых n эффективнее работает обычный метод.

Правильно, ответит математик, график функции n2 в начале растет медленнее, чем  nlogn,  а точка пересечения зависит от аддитивной и мультипликативной константы в формулах.

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

Для операции умножения доказано, что существующие алгоритмы неулучшаемы, то есть они не могут пробить уровень O(nlogn). А с учетом прочих затрат, например, памяти, можно сказать, что умножение использует полностью O(n2) вычислительных ресурсов.

Тогда, целесообразно ввести измерение алгебраических операций и функций по степени потребления ими вычислительных ресурсов, разумеется, если для них известны неулучшаемые алгоритмы.

Итак, пусть известно, что для функции f существует, как минимум один, неулучшаемый алгоритм ее вычисляющий, и сложность алгоритма есть O( nm ), то сложность ( S ) этой функции будет m ,

                                                                S( f ) = m .                                                              (1.1)

Для арифметических операций сложения  + , умножения  *  и возведения в степень  ^  известны их неулучщаемые алгоритмы, поэтому

                                               S( + ) = 1, S( * ) = 2, S( ^ ) = 3.                                             (1.2)

Ассоциации получаются такие: сложение - линейная операция, умножение - квадратная, степень – кубическая. Алгоритмы, соответственно, однопроходные, двухпроходные и трехпроходные.

Подобная грубая классификация позволяет избавиться от учета объема входных данных n при анализе вычислимых функций и алгоритмов.

В каких случаях можно свернуть время в память?

Во многих случаях, особенно там, где в алгоритмах присутствуют операции, похожие на сложение и умножение (1.2). Дело в том, что обычное сложение и умножение это две симметричные коммутативные операции, назовем их жидкими, поэтому эффекта O( nm ) O( nm -1 log n ) можно добиться за счет использования обеих операций в равных дозах. Такой прием окрестим сливом коммутативности.

 

              

 


The Programs And Source Codes Rambler's Top100 Rambler's Top100