e-Hector, Смотри, когда в твоем алгоритме перебирается вся матрица.
for i:=1 to m do
for j:=1 to m do
Потом производится сравнение индексов столбца и строки.
if i=j then
Если это так, то i = j т.е. при адресация элемента массива a[ I ,
J ] и a [ I,
I ] не имеет различий в силу выполнения означенного условия.
Из всего массива размерностью N, содержащего N^2 элементов, выберется только диагональ, т.е. N элементов.
N^2 - N сравнений будет проделано впустую. Условие не выполнится.
Конечно для современных ПК на малых размерностях это тьфу. Но если мы возьмем куб размерность в пару миллионов, то будет швах!
Берем определение главной диагонали.
Цитата e-Hector:
|
Главную диагональ квадратной матрицы образуют элементы с одинаковым индексом строки и столбца »
|
образуют элементы с
одинаковым индексом строки и столбца.
Диагональю мы можем назвать
линию начинающуюся с элемента 1;1 и заканчивающуюся элементом N;N. При условии равенства индексов.
Если рисовать на листе бумаги, то при стандартном расположении (осей X вправо Y вверх) (заметь матрица будет перевернута) это будет прямая
f(y)=x
Так может ее проще нарисовать, чем сравнивать все точки плоскости на принадлежность к линии?
Наглядный пример:
Мы можем нарисовать кривую y=ax^2+bx+c (парабола). А можем анализировать все точки плоскости с точностью отклонения до Е(эпсилон) от заданной кривой.
Соотв. порядки трудозатрат будут существенно различны.
