优化、时间复杂度和流程图（Scilab）

Question

我试图优化这段代码，但是已经不可能再优化了。

请帮助构建此算法的流程图。

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)
但我还不确定。

我做不到

复杂度函数（最坏情况）

和

最差计算复杂度： ()

Answer 1

这好像是作业 ;p

至于时间复杂度，它看起来更像是 O(n²) 因为你有一个 for 循环，在另一个 for 循环中。我最近开始在 Udemy 上观看我强烈推荐的关于算法和数据结构的课程。他很好地解释了 BigO 符号 :) Link 当然。（与作者无任何关系）

Answer 2

"Optimization" 取决于您的目标，例如您可能希望最小化浮点运算的数量或最小化 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)

此处计算机运算次数与原代码大致相同，但执行时间快了很多倍：

令 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

Answer 3

就优化而言，您应该考虑到 Scilab（及其同类数学编程语言 MATLAB 和 Octave）本质上是矢量化的。这意味着如果您使用了太多 for loops，您可能应该回去阅读一些文档和教程。您编写的代码的规范版本可以实现为：

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.

优化、时间复杂度和流程图（Scilab）

Optimization, time complexity and flowchart (Scilab)

optimization

time-complexity

shortcode

scilab

flowchart