Оптимизация, сложность времени и блок-схема (Scilab) - PullRequest
Новая
       20

Оптимизация, сложность времени и блок-схема (Scilab)

0 голосов
/ 08 января 2020

Я пытался оптимизировать этот код, но больше невозможно оптимизировать.

Пожалуйста, помогите с построением блок-схемы для этого алгоритма. 

A = [-1,0,1,2,3,5,6,8,10,13,19,23,45];
B = [0,1,3,6,7,8,9,12,45];
N1 = length(A);
N2 = length(B);
t = 1;
m = 10;
C = [];
for i=1:N1
    for j=1:N2 
        if A(i)==B(j)
            break
        else
            if j==N2
               C(t)=A(i);
               t=t+1;
           end
       end
   end
end
disp(C);
N3=length(C);
R = [];
y = 1;
for l=1:N3
    if C(l)>m
       R(y)=C(l);
       y=y+1;
   end 
end
disp(R);

Как найти временную сложность алгоритма

Мне кажется, это должно быть O (n).

Доминирующая (элементарная) операция: сравнение A (i) == B (j)
Но я пока не уверен.

И я не могу сделать

Функция сложности (наихудший случай)

и

Наихудшая сложность вычислений: ? (?)

Ответы [ 3 ]

1 голос
/ 10 января 2020

«Оптимизация» зависит от вашей цели, например, вы можете минимизировать количество операций с плавающей запятой или минимизировать количество инструкций Scilab или минимизировать время выполнения алгоритма.

Поскольку Scilab является При помощи интерпретации языка можно сократить время выполнения и длину кода, применяя векторизацию.

Например, ваш код 

N3=length(C);
R = [];
y = 1;
for l=1:N3
    if C(l)>m
       R(y)=C(l);
       y=y+1;
     end 
end

может быть переписан: 

R=C(C>m)

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

Let C = rand (1,1000); m = 0,5; 

--> timer();R=C(C>0.5);timer()
ans  =
   0.000137

--> timer();
-->   N3=length(C);
-->     R = [];
-->     y = 1;
-->     for l=1:N3
  >         if C(l)>m
  >            R(y)=C(l);
  >            y=y+1;
  >         end 
  >     end

 --> timer()
 ans  =
    0.388749
0 голосов
/ 16 января 2020

Что касается оптимизации, вы должны учитывать, что Scilab (и его коллеги по языкам математического программирования MATLAB и Octave) изначально векторизованы. Это означает, что если вы используете слишком много for loops, вам, вероятно, следует go вернуться назад и прочитать некоторую документацию и руководства. Каноническая версия написанного вами кода может быть реализована следующим образом: 

A = [-1, 0, 1, 2, 3, 5, 6, 8, 10, 13, 19, 23, 45];
B = [0, 1, 3, 6, 7, 8, 9, 12, 45];

C = setdiff(A, B);
disp(C);

m = 10;
R = C(C > m);
disp(R);

Результат:

-1. 2. 5. 10. 13. 19. 23.

23.
0 голосов
/ 09 января 2020

Похоже, что это, вероятно, домашнее задание; p

Что касается сложности времени, это выглядит как O(n²), поскольку у вас есть для l oop, внутри другого для l oop. Недавно я начал смотреть этот курс об алгоритмах и структурах данных в Udemy, который я очень рекомендую. Он хорошо объясняет нотацию Bi gO :) Ссылка на курс. (Нет принадлежности к автору)

...