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

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

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

Анализ алгоритмов — это изучение характеристик и эффективности алгоритма. Такой тест на производительность.

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

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

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

2. Пространственная сложность — это параметр, определяющий сколько памяти потребляет алгоритм. 

Ресурсы наших умных машин тоже не безграничны, память имеет вполне определенный размер. Представим, что алгоритм работает исправно, выдает нужные результаты. Но при этом он сложный, простые задачи разбиты на множество действий, каждое требует памяти. И в итоге мы снова ждем решения простых задач часами из-за перегруженной памяти. 

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

Умение анализировать предложенные алгоритмы обязательно проверят на практике в решении задач ОГЭ и ЕГЭ по информатике. Применять навыки анализа придется в заданиях разного типа. 

Рассмотрим на примерах, как можно решить экзаменационные задачи на анализ алгоритмов. Здесь важно не просто решить задачу, а понять, как работает алгоритм, и почему он делает это именно так.

Задача: На вход алгоритма подается натуральное число N. Алгоритм строит по нему новое число R следующим образом. 

1. Строится двоичная запись числа N.

2. Далее эта запись обрабатывается по следующему правилу:

а) если сумма цифр двоичной записи числа четная, то к этой записи справа дописывается 0, а затем два левых разряда заменяются на 10;

б) если сумма цифр двоичной записи числа нечетная, то к этой записи справа дописывается 1, а затем два левых разряда заменяются на 11;

Полученная таким образом запись является двоичной записью числа R.

3. Результат переводится в десятичную систему и выводится на экран.

Например, для исходного числа 6 = 1102 результатом является число 10002 = 8, а для исходного числа 4 = 1002 это число 10112 = 13.

Вопрос: Укажите минимальное число N, после обработки которого с помощью этого алгоритма получается число R, больше 50. В ответе запишите это число в десятичной системе счисления.

Решение: Для решения этой задачи нам нужно перевести предложенный алгоритм на язык нашего компьютера. В нашем примере мы будем использовать Python.

1. Для начала проверим, как работает программа, используя значения из примера:

1 N = int(input())

2 n = bin(N) [2:]

3 S = sum( [int(x) for x in n])

4 if s % 2 == 0:

5   n = ‘10’ + n[2:] + ‘0’

6 else:

7   n = ‘11’ + n[2:] + ‘1’

8 r = int (n, 2)

9 print (r)

При вводе числа 6 программа должна вернуть ответ 8.

При вводе числе 4 программа должна вернуть ответ 13.

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

1. Нам нужно найти такое минимальное N, при котором после обработки R будет больше 50. Вот как это сделать:

  1 for i in range (1, 100):

  2 N = i

  3 n = bin(N) [2:]

  4 S = sum( [int(x) for x in n])

  5 if s % 2 == 0:

  6   n = ‘10’ + n[2:] + ‘0’

  7 else:

  8   n = ‘11’ + n[2:] + ‘1’

  9 r = int (n, 2)

10 if r > 50:

11  print (i)

12  break

Запускаем программу и она выводит результат 19, который мы и запишем в ответ. Это наше минимальное число N.

Задача: Какая строка получится в результате применения приведенной ниже программы к строке, состоящей из 100 идущих подряд цифр 9? В ответе запишите полученную строку.

НАЧАЛО

ПОКА нашлось (33333) или нашлось (999)

     ЕСЛИ нашлось (33333)

          ТО заменить (33333, 99)

          ИНАЧЕ заменить (999, 3)

     КОНЕЦ ЕСЛИ

КОНЕЦ ПОКА

КОНЕЦ

Решение: Итак, нам снова нужно перевести предложенный алгоритм на язык Python.

1 s = 100 * ‘9’

2 while ‘33333’ in s or ‘999’ in s:

3    if ‘33333’ in s:

4      s = s.replace(‘33333’, ‘99’)

5    else:

              s = s.replace(‘999’, ‘3’)

7 print(s)

После этого запускаем программу и получаем решение — нужную нам строку 99339. Это значение мы и записываем в ответ.

Анализ алгоритмов — это

– тест на производительность алгоритма и изучение его характеристик;

– замена плохого алгоритма на хороший;

– тест на знание алгоритмов.

Какие два основных параметра изучается при анализе?

– временная сложность и математическая сложность;

– временная сложность и пространственная сложность;

– профессионализм разработчика и время на написание алгоритма.

Какая строка получится в результате применения приведенной ниже программы к строке, состоящей из 20 идущих подряд цифр 8? 

НАЧАЛО

ПОКА нашлось (444) или нашлось (88)

     ЕСЛИ нашлось (444)

          ТО заменить (444, 8)

          ИНАЧЕ заменить (88, 4)

     КОНЕЦ ЕСЛИ

КОНЕЦ ПОКА

КОНЕЦ

– 484;

– 488;

– 8484.