Алгоритмическая сложность. Лирическое отступление.

[Organon]

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

Задача формулируется очень просто: определить, является заданное число простым или составным.

Если у нас нет свидетеля, точнее, кандидата на роль делителя, на который нам достаточно поделить, чтобы убедиться, что это на самом деле делитель, — наша задача перебрать все простые числа, которые гипотетически могут претендовать на роль делителя. На самом деле, боюсь, легче проверять все числа подряд, а не только простые. Перебирать достаточно числа, не превосходящие квадратного корня из данного числа.

О! Вот тут вопрос для самопроверки))))

Вопрос. Определить класс сложности этого алгоритма (алгоритма "перебора делителей") в терминах О-нотации, или вообще в каких бы то ни было терминах.

Вообще на самом деле, поскольку большие простые числа очень активно используются в криптографии, то важно иметь быстрые алгоритмы, которые помогают определить, простое число перед нами, или составное. Такие алгоритмы называются тестами простоты.
Те, кто ответит на вопрос для самопроверки, убедятся, что сложность самого простого и естественного, с первого взгляда, алгоритма значительно превосходит полиномиальную. Однако, человеческая мысль не стоит на месте. Разработано достаточно много полиномиальных тестов простоты. Однако сами эти алгоритмы (простите за каламбур) не так уж просты!
Причем, то, что задача проверки на простоту полиномиально разрешима в общем виде, было доказано только в 2002 году! Однако предложенный детерминированный алгоритм оказался достаточно сложным, и это, конечно, сильно затрудняет его применение!

И вообще, здесь, конечно, палка о двух концах: чем больше мы пытаемся упростить алгоритм в терминах алгоритмической сложности, тем больше мы запутываем сам алгоритм, и, как следствие, код программы, пока он не станет совершенно нечитабельным!
***
Я читала где-то (очень давно, правда, в те времена, когда машины были не столь быстры, и время работы даже маленькой программы существенно зависело от ее структуры), что для ускорения хода работы программы желательно все циклы насколько это возможно писать линейно!
О чем я? Вот, представьте, у нас есть массив, состоящий из десяти элементов. Нам нужно каждому элементу присвоить его порядковый номер, умноженный на два.
Массив — это такая структура данных: как длинный ящик с перегородками, делящими его на ячейки. Название у него одно, но в каждой ячейке лежит своё значение.
Вот, например, пустой массив с именем А:

Название каждого его элемента состоит из двух частей: имени всего массива (А) и своего личного порядкового номера (нечто вроде адреса его проживания).
Все элементы массива должны иметь одинаковый тип данных. (На самом деле, тут всё чуть сложнее, но сейчас речь не об этом). В нашем случае "имеют одинаковый тип данных" означает, что все элементы могут быть либо числами (все сразу), либо строками (тоже все сразу). Если числами, то либо все они хором целые, либо вещественные, либо еще всякие и разные (а бывает их в машинном представлении много). Главное, что все десять значений могут быть только какого-то одного типа.
И вот теперь представьте, что нам нужно в каждую такую ячейку положить число.
Как я уже говорила, к примеру, число, вдвое большее номера каждого элемента. То есть в первую ячейку положить двойку, во вторую — четверку, в третью — шестерку, и т.д.

Обычно это делается в цикле, который на псевдоязыке выглядит следующим образом:

для i от 1 до 10 с шагом 1
А_i = i*2
конец цикла

i — это вспомогательная переменная, называемая счетчиком цикла. Она пробегает все значения от 1 до 10 с шагом 1 (то есть цикл обернется вокруг себя 10 раз), и в каждый элемент массива положится его значение.

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

Вот такой алгоритм считал бы (почти) вдвое быстрее:

для i от 1 до 9 с шагом 2
А_i = i*2
А_i+1 = (i+1)*2
конец цикла

Что мы здесь сделали?
Мы за каждый проход цикла стали вычислять не одно значение массива, а сразу два. Тем самым цикл укоротился вдвое (хотя тело его удлинилось, но это как раз менее существенно).

А вот такой алгоритм будет работать еще быстрее:

для i от 1 до 6 с шагом 5
А_i = i*2
А_i+1 = (i+1)*2
А_i+2 = (i+2)*2
А_i+3 = (i+3)*2
А_i+4 = (i+4)*2
конец цикла

Здесь у нас получится всего два прохода цикла вместо 10. (Нетрудно проверить, что результат у всех трех алгоритмов будет один и тот же!)
И наконец, самым быстрым будет вот такой вот линейный алгоритм:
А₁ = 2
А₂ = 4
А₃ = 6
А₄ = 8
А₅ = 10
А₆ = 12
А₇ = 14
А₈ = 16
А₉ = 18
А₁₀ = 20

Не шучу!
Это хорошо, когда известно заранее, сколько нам надо сделать шагов! Если же нет (мы не знаем длины массива до определенного времени), то без цикла всё же не обойтись, но предлагается делать его "большими шагами", как показано для случаев с шагом 2 и 5.

И вот, представьте, это задача не просто элементарная, а наипростейшая! Что же говорить о задачах сложных! Чтобы понизить алгоритмическую сложность, сами алгоритмы, и тексты соответствующих им программ усложняют до немыслимой степени! И разобраться в них зачастую очень и очень непросто.

Кроме того, возвращаясь к проверке больших чисел на простоту. Тут нас поджидает еще одна, на этот раз техническая проблема. В компьютере могут храниться разные типы данных. Каждый числовой тип, даже самый "вместительный" может хранить числа до какого-то максимального значения. А дальше — стоп! Переполнение! Numeric Overflow! И поэтому помимо всех вышеизложенных проблем, стоит еще проблема представления больших чисел и их обработки!
Можете себе представить? Мы вынуждены хранить число не целиком, а кусочками, и тем не менее нам нужно узнать, поделится оно на что-нибудь или нет! О-о-о! Здесь всё совсем непросто!

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