Оценка вычислительной сложности алгоритма [MatLab]

[Alimoe93]

Всем привет! В общем вопрос может показаться легким, но к сожалению для меня он не так тривиален, как кажется. Собственно хотелось бы оценить вычислительную сложность алгоритма, но в силу моих скромных знаний (абсолютно "нулевых") не имею возможности верно провести оценку. Для справки: язык - MatLab.

PHP код:

NQ=10000;
Nel=10;
% OKM - матрица 10x10
for m2=1:NQ 
    tetta = -pi/2+ pi/NQ*m2;  
         for m3=1:Nel
         V(m3,1)=exp(i*pi*(m3-1)*sin(tetta));
         end
      V1=V';
      Q(m2)=1/(V1*OKM*V);
end 


P.S. Да, литературу по данному вопросу читал. Но хотелось бы услышать людей, которые в этом чувствуют себя, как рыба в воде.

[Pavia]

Параметры NQ, Nel.
Берём самую операцию относительно какой будем считать.
В данном случае умножение - T0.

V(m3,1)=exp(i*pi*(m3-1)*sin(tetta));

1)

m3-1

Время выполнение O1(1) так как не зависит от параметров.
Тоже самое можно доказать другим путём.
Вычитание вычитание относительно умножения по времени занимает с*T0
c некоторая константа, если умножение делают через сложение то с=1/64 на 64 битном компьютере. Мы можем заменить оценкой сверху T0.
2)

i*pi*(m3-1)*sin(tetta)

sin(tetta) - фиксирована, постоянная внутри цикла.
Итого имеем 4-операции выполняемые
отсюда время выполнение T1=4*T0
По свойствам O() константа убирается.
O(1) для данной строчке.
O2(1) <=> 4*T0
3)

         for m3=1:Nel 
         V(m3,1)=exp(i*pi*(m3-1)*sin(tetta)); 
         end

O3(Nel) <=> Nel*O2(1)
4)

V1=V';

Транспонирование вектора операция линейная.
O4(Nel) <=> Nel*T4;
5)

Q(m2) =1/(V1*OKM*V);

Умножение матрицы на вектор операция квадратичная.
T5_1=2*Nel^2*T0
Умножение вектора на вектор операция линейная.
T5_2=2*Nel*T0
T5=T5_1+T5_2
Оценка сверху для T5_1 всегда больше T5_2б поэтому можем сделать замену оценкой сверху.
T5Up=T5_1+T5_1=2*T5_1=4*Nel^2*T0
Константа по правилам O() убирается
O5(Nel^2)<=>4*Nel^2*T0
6) Чуть не пропустил строчку.

tetta = -pi/2+ pi/NQ*m2;

Тут вы уже знаете
"-pi/2" - константа
pi/NQ - выполняется за c1*T0
-pi/2+ pi/NQ*m2 - выполняется за c2*T0
T6=c1*T0+T0+C2*T0=(1+c1+c2)*T0
По правилам O() если время не зависит от параметра то O ()- константан
O6(1)
7)

for m2=1:NQ  
    tetta = -pi/2+ pi/NQ*m2;   
         for m3=1:Nel 
         V(m3,1)=exp(i*pi*(m3-1)*sin(tetta)); 
         end 
      V1=V'; 
      Q(m2)=1/(V1*OKM*V);

O7(?)=NQ*(O6(1)+O(Nel)+O(Nel^2));
По правилам O() заменяем наибольшей степенью.
O7(?)=NQ*O(Nel^2)
Отсюда
O7(NQ*Nel^2)

Ответ сложность алгоритма O(NQ*Nel^2).

[Alimoe93]

Спасибо за ответ! Подскажи, если руководствоваться мыслями из данной статьи, то ответ будет O(NQ*Nel). В чем я ошибаюсь?
https://habrahabr.ru/post/104219/

[Pavia]

В данном коде по знаком '*' и ' прячется вызов функций. Вы этого не учли.
Скорость исполнения определяет самая медленная функция/операция. А в матлабе операторы имеют асимтотическую сложность, а не постоянную.

[Alimoe93]

Еще раз спасибо! Не могли бы вы проверить мои мысли, относительно другого алгоритма?

%En - матрица [Nel x (Nel-z)];

for m2=1:NQ 
    tetta = -pi/2+ pi/NQ*m2; 
         for m3=1:Nel
         V(m3,1)=exp(i*pi*(m3-1)*sin(tetta));
         end
      V1=V';
      QS(m2)=1/(V1*En*En'*V);
end

Строчка:

QS(m2)=1/(V1*En*En'*V);

1) V1*En - умножение вектора на матрицу, т.е. O(Nel^2) (входе умножения получается вектор);

2) (V1*En)*En' - опять же получается умножение вектора на матрицу, т.е. O(Nel^2) (входе умножения получается вектор);

3) [(V1*En)*En']*V - умножение вектора на вектор, т.е. O(2*Nel).

Итого: O(Nel^2+Nel^2+2*Nel)*O(NQ)=O(NQ*Nel ^2), верно?

[Pavia]

Да верно. Только забыли шрих, транспонирование матрицы En.

[Alimoe93]

Спасибо!

[mike84]

Всем добрый день!
Вопрос по теме. Хотел бы сам научиться определять вычислительную сложность алгоритма. Это нужно для моей научной работы в области радиосвязи. Но из приведенного выше примера пока еще не все понял, так как в изложенном коде были перечислены не все математические операции. Имею код в MATLAB:

for m=1:col_R
     d(:,m)=norm(Y2-Y1*constel_diff(:,:,m),'fro');
end

Y2, Y1, constel_diff(:,:,m) - комплексные матрицы 2*2;
Операция norm(Y,'fro') - норма Фробениуса, которая означает корень из суммы квадратов модулей каждого из элементов матрицы.
constel_diff(:,:,m) - таких матриц определенное количество m, каждая из которых подставляется в выражение.
В итоге получаем строку из значений d(:,m), которая нужна для дальнейших расчетов.

[mike84]

Да, и вопрос, как относится к действиям: деление, комплексное сопряжение, модуль, сравнение, возведение в степень? Потому как в сети полно только простых примеров с квадратными уравнениями.