Время работы алгоритмов

[Amicus Plato]

Напишу про то, зачем же нам всё-таки нужно понижать алгоритмическую сложность. Казалось бы, машины быстрые, процессоров у них тоже может быть много. Неужели действительно так остро стоит проблема времени?

Давайте посмотрим.
Думаю, в детстве многие сталкивались с таким примером (на самом деле когда-то поразившим мое воображение!). Когда объясняют, что же такое большие числа, часто, чтобы помочь оценить масштаб, делают это таким способом.
Представьте что вы начинаете вслух считать до миллиарда. Миллиард — это всего лишь единичка и девять нулей. Число не такое уж и большое. 1 000 000 000.
И вот, представьте, что считаете вы размеренным голосом, и каждую секунду произносите очередное число. (Пока числа маленькие, вы можете не спешить: ...двадцать один, двадцать два, двадцать три.... вполне можно успеть. Дальше, однако, будет сложнее. Чтобы произнести число четыреста восемьдесят девять миллионов восемьсот пятьдесят четыре тысячи триста девяносто один, секунды уже маловато, но мы всё равно попробуем!)
Так вот, элементарные подсчеты показывают, что если мы будем считать без сна и отдыха, без перерыва на еду, и даже не позволим себе глотка воды, у нас на это уйдет 31,7097919837645865043125317097921 год.
То есть где-то 31 год и восемь с половиной месяцев, если я нигде не ошиблась.
Некоторые из нас еще даже не дожили до этого возраста)))
То есть, начни они считать во младенчестве, сейчас бы еще находились в пути... )))

Но машины, конечно же, считают быстрее!
Вот, возьмем не очень быстрый процессор с тактовой частотой 1 ГГц. Гигагерц — это как раз 10⁹ герц, или тактов в секунду. Значит, наш компьютер может просчитать "в уме" до миллиарда за секунду (если мы будем считать, что один такт соответствует "произнесению" одного числа). Да, так гораздо быстрее, чем если бы мы делали это сами!
Но вот вернемся к задаче, которую я приводила раньше:
Дано число: 15256677987889881453. Проверить, является оно простым или составным.
Число для удобства напишу так:
15 256 677 987 889 881 453
Оно содержит 20 знаков. (И это на самом деле не очень большое число!)
Корень из этого числа будет состоять из десяти знаков (то есть как раз соответствовать нескольким миллиардам).
Чтобы проверить, делится ли наше число нацело, нужно эти самые несколько миллиардов раз проделать ряд однотипных действий. Хорошо, если наше число не настолько велико, что умещается в одной переменной.
Тогда достаточно такого алгоритма:

1. N=3905979774 (это приблизительное значение квадратного корня)
2. для i=1 до N (начинаем цикл)
3. остаток=остаток_от_деления(15 256 677 987 889 881 453 на i) (функция "остаток_от_деления" выдает остаток от деления проверяемого числа на каждое очередное значение счетчика i)
4. если остаток=0 то (если остаток = 0, то число поделилось нацело, и мы сразу получили ответ)
5. печать: i (печатаем делитель)
6. выход (выходим из программы)
7. всё если
8. конец цикла (здесь происходит увеличение счетчика на единицу и возврат на начало)

Итого в худшем случае (если мы не найдем делителя раньше), нам нужно повторить 4 действия — строчки с номерами 2, 3, 4, 8 (и даже чуть больше, потому что надо еще анализировать, где нам встретится строчка конца условия 7: "всё если"). То есть, давайте считать это за 5 действий. Итак 5 действий надо выполнить без малого четыре миллиарда раз. Итого 20 миллиардов. По одному миллиарду в секунду.
20 секунд для такой простенькой задачи — это очень немало!

Вот, к примеру, каковы реалии. И, думаю, это на сегодняшний день уже устаревшие данные.
В статье "Простота и совершенство" я уже об этом упоминала.
Наибольшим известным простым числом по состоянию на сентябрь 2006 года является 2^32582657 − 1. Оно содержит 9 808 358 десятичных цифр!

Не десять цифр, как то число, которое мы рассматривали сейчас, а без малого десять миллионов цифр! Представляете сколько считал бы наш алгоритм?
В миллион раз дольше!
20*1 000 000 =20 000 000 секунд = 5555, (5) часов = 231,(481) суток!!!
Теперь понятно, почему хочется сделать это чуть быстрее)))

Правда, как раз для чисел Мерсенна, которые представляются в виде степени двойки минус единица, существуют быстрые алгоритмы проверки их на простоту. С остальными дело обстоит совсем не так просто.

@темы: Алгоритмы, Искусственный интеллект, Поп-математика, Amicus Plato

Comments

[J.Random]

Наверное, стоит отметить, что в криптографии иногда необходимо сделать с точностью до наоборот: так поставить задачу, чтобы понизить сложность алгоритма ее решения было невозможно.

[Amicus Plato]

Black_Diver о, да )))
поэтому если кто-то всё-таки докажет, что P=NP — это будет означать полный крах современной криптографии ))
Не сразу, наверное — самого доказательства мало, нужны еще и методы соответственные, но тогда рано или поздно — пиши - пропало! Всё придется заново перешифровывать. Да еще и непонятно, какими методами...
Поэтому конечно было бы желательно, чтобы кто-то доказало противное: P!=NP. Правда непонятно, дадут ли за это обещанную премию (обещана она, вроде, тому, кто докажет равенство). Хотя как раз в случае неравенства доказавшего надо бы озолотить! )))