Приходит на ум аналогия из некомпьютерной тематики, связанная с установлением хозяина ключей, найденных вблизи многоквартирного дома. Скорее всего, поиск квартиры и владельца придется вести последовательно: от подъезда (столбца таблицы) к подъезду, и внутри очередного подъезда - по этажам (строкам). Если дом велик, то процесс, трудоемкость которого сопоставима с количеством квартир, может затянуться, и энтузиазм иссякнет.

К счастью, для решения нашей задачи можно предложить более экономичные алгоритмы, а именно: разлагать входное значение на всевозможные пары сомножителей и проверять их. Так, для n = 30 найдется несколько пар-претендентов: (1, 30), (2, 15), (3, 10), (5, 6), (6, 5), (10, 3), (15, 2) и (30, 1). Сразу отсеиваются пары, включающие числа, большие 9. Соответственно, остаются только (5, 6) и (6, 5). Иначе говоря, вместо алгоритма поиска используется некоторый вычислительный механизм.

В данном примере, когда разрешенный диапазон ограничен узкими рамками нашей таблицы, задача элементарно решается "в уме". Но с ростом n проблема усложняется и желательно прибегнуть к какому-нибудь эффективному механизму. Частично нас выручит - вероятно, знакомый вам - алгоритм Евклида.

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

В наших рассуждениях мы уже несколько раз меняли структуру данных, предназначенную для представления таблиц умножения. Чаще всего это диктовалось желанием уменьшить емкостную сложность алгоритма, выделив меньше места для хранения данных. Если при этом ставить целью не терять данные, - именно так стоял вопрос при переходе от представления на рис. A5-3 к рис. A5-4, - то возможным подходом будет установление взаимно однозначного (поэлементного) соответствия между различными представлениями. Тогда от одной структуры к другой мы можем переходить без ущерба для содержимого набора данных. Примерно по такой схеме осуществляется квартирный обмен.

Удобно, если переход от одной структуры к другой удается описать одной формулой. Но часто подобные преобразования реализуются многошаговым алгоритмом. Следовательно, при замене "структуры пользователя" на структуру данных в программе для ЭВМ, следует учесть накладные расходы - машинное время - на реализацию алгоритма преобразования. Заметим, что временнАя сложность такого преобразования в одну сторону может заметно отличаться при обратном преобразовании.