Оценка времени работы алгоритмов
Для перемножения двух β - битовых чисел обычным методом потребуется
количество битовых операций ~ θ (β2)
Размер входных данных определяется не количеством данных,
а количеством битов для их записи.
Задача разработчика : создать такой алгоритм,
который бы выполнял арифметические операции за
наименьшее время.
Наиболее значимые алгоритмы: Поиск простых и
составных чисел, поиск общих делителей и наибольших
общих делителей, разложение числа на множители,
кодирование и декодирование чисел, генерация случайных
чисел.
Для обработки целых чисел надо всегда помнить о
представлении целого числа в позиционной системе счисления:
где ai – цифры системы счисления
n –количество цифр в записи числа