Эффективность алгоритмов

мне сообщили что на марс отправляют новый марсоход и представьте что нам доверили написать для этого марсохода программу которая проверяет является ли данное число простым скажем канал общения зашифрован алгоритмом р.с. эй и марсоходу требуется сделать предварительные тесты при разработке марсоходы любого космического устройства необходимо минимизировать массу и потребление энергии каждой детали модули должны быть максимально легкими а система потреблять как можно меньше электричества и перед нами стоит очень непростая задача потому что нам придется иметь дело с вот такими числами и обрабатывать их очень быстро если нам дать небольшое число например 90 наш алгоритм должен проверить его почти так же быстро как и все это число то есть с увеличением водных данных не должно быть значительных задержек теперь проверяем является ли число n простым или составным возьмем множество всех чисел до н если n100 то множество будет от 2 до 100 и наш алгоритм будет проходить по этому множеству чисел и в каждой точке наш алгоритм будет отвечать на вопрос нужно ли проводить тесты например берем число а и пытаемся разделить n на а мы подставляем а вот в такое выражение и смотрим равняется ли остаток нулю если да то а делитель н а значит что мы на сто процентов уверены что число составное в противном случае мы должны продолжить поиск пока не узнаем простое это число или составное число можно сказать что вот здесь у нас будет стена и она равна корень квадратный из n если мы не уверены что н это простое число тогда нам придется перебрать все числа пока мы не дойдем до корня из n и только тогда мы скажем что н это точно простое число и мы в этом они а если n квадрат простого числа скажем 7 на 7 49 если в алгоритм ввести 49 тогда нам снова придется перебрать все числа до корня из n можно например рассмотреть такой вариант если два не является делителем то тогда можно исключить из проверки все числа кратные двум ведь все наши алгоритмы каждый раз сделал по одному шагу но мы можем использовать известные нам закономерности составных чисел например если наше число делится на 2 то оно составное а двойка это простое число то есть 4 6 8 10 заведомо составные числа и тогда мы можем сократить наше время на проверку в два раза и уменьшить пространство обхода то есть исключить все четные числа и проверять на корень из n все нечетные также мы можем найти и другие закономерности составных чисел тем самым и ещё больше сократить пространство обхода например найдем делитель если мы найдем а которая даст понять что n составное то есть можно сократить время работы алгоритма если сразу выйти из цикла и найти делитель это значит проверка закончена мы на сто процентов уверены что число составное и алгоритму завершается он заканчивает работу дальше нет смысла перебирать ранее остановка алгоритма это хорошо но оно не подходит в том случае если n простое а теперь давайте посмотрим наглядно насколько эти улучшения сокращает нам поиск если не придется перебирать все возможные делители то в зависимости от компьютера сократится и время поиска я написал программу чтобы наглядно это продемонстрировать с ее помощью мы можем сравнить два алгоритма с точки зрения количества шагов проделанных во время их выполнения слева алгоритм а который проверяет все возможные делители от 2 до корня из n а справа алгоритму назовем его продвинутый алгоритм в нем я исключил всех родные двойки делители и уменьшил перебор вдвое а еще я прописал в алгоритме б ранее завершение он не идеален просто я применил в нем пару улучшений для наглядного сравнения давайте я немного поиграю с входными данными я меняю исходное число справа вверху пишется результат составное или простое а снизу количество шагов и первое что бросается в глаза в каждом втором случае алгоритму б достаточно одного шага мы знаем почему так если число чётное как вот это алгоритма становится сразу на двойки старый алгоритм проверил 314 делителей а новому алгоритму достаточно одного проверить делимость на двойку очень неплохая оптимизация однако с увеличением исходного числа растет и количество шагов столбец растет и становится красным пока не достигнет лимита вот эта красная линия ограничитель если столбец дойдет до неё то марсоход сломается а браузер может зависнуть попытаюсь к ней приблизиться вот столбец достигнул линии и все работает очень медленно я прямо чувствую как браузер вот-вот вылетит или зависнет обратите внимание что продвинутому алгоритму понадобилось всего два шага но помните про худший случай у меня здесь для примера заготовлено несколько больших простых чисел мы должны справляться с любым числом мы не знаем какие данные нам в виду и если вести большое простое число смотрите что случится алгоритм б как мы помним делает вдвое меньше проверок но шагов все равно получилось очень много потому что это тот самый худший случай мы подходим к черте но и число еще не очень большое гораздо меньше 15 цифр если я веду в наш алгоритм простое 12 значное число посмотрим что будет все тормозит и кажется что вот-вот сломается смотрите что случилось оба алгоритма сильно превысили имеет ничего не вышло продвинутый алгоритм все еще недостаточно хорош но теперь мы понимаем что именно надо улучшать это количество шагов для худшего случая и у нас есть отличный инструмент чтобы наглядно видеть рост количества шагов в зависимости от исходного числа по ссылке в описании вы можете посмотреть как здесь все устроено и можете запрограммировать свой алгоритм и сравнить насколько вы улучшили его по сравнению с изначальным спасибо что подписывайтесь на наш канал мы будем рады услышать ваше мнение по поводу этого видео если у вас возникли вопросы касательно данного видеоролика то напишите их в комментариях и мы с удовольствием постараемся ответить на них