14 - Сложность вычислений

1. Задан массив X[1..N]. Определите число операций сложения, которые выполняются при работе этой программы:
  S:=X[1]+X[N];
  for k:=1 to N do
    X[k]:=X[k]+X[k]+S;
Для обозначения операции умножения используйте символ *.
Ответ: 
2. Задан массив X[1..N]. Определите число операций умножения, которые выполняются при работе этой программы:
  S:=X[1]*X[N];
  for k:=1 to N do begin
    X[k]:=2*X[k]+S;
    for i:=1 to 3 do
      S:=S*2;     
  end;
Для обозначения операции умножения используйте символ *.
Ответ: 
3. Задан массив X[1..N]. Определите число операций сложения, которые выполняются при работе этой программы:
  S:=X[1]+X[N]+3;
  for k:=1 to N do
    for m:=1 to N do
      X[k]:=X[k]+S;
Для обозначения операции умножения используйте символ *.
Ответ: 
4. Задан массив X[1..N]. Определите наиболее точную оценку временной сложности алгоритма:
  S:=X[1]+X[N];
  for k:=1 to N do
    for m:=1 to 5 do
      X[k]:=X[k]+S;
O(log N)
O(N)
O(N2)
O(N3)
O(2N)
5. Задан массив X[1..N]. Определите наиболее точную оценку временной сложности алгоритма:
  S:=X[1]+X[N];
  for k:=1 to N do
    for m:=1 to k do
      X[k]:=X[k]+X[m]+S;
O(log N)
O(N)
O(N2)
O(N3)
O(2N)
6. Задан массив X[1..N]. Определите наиболее точную оценку временной сложности алгоритма:
  S:=X[1]+X[N];
  for k:=1 to N do
    for m:=1 to N do
      for q:=1 to k do
        X[k]:=X[k]+X[q]+S;
O(log N)
O(N)
O(N2)
O(N3)
O(2N)
7. Задан массив X[1..N]. Определите наиболее точную оценку временной сложности алгоритма:
  function Rec(N: integer): integer;
  begin
    Rec:=0;
    if N > 3 then
      Rec:=Rec+Rec(N-1)+2*Rec(N-2);
  end;
O(log N)
O(N)
O(N2)
O(N3)
O(2N)
8. Задан массив X[1..N]. Определите наиболее точную оценку временной сложности алгоритма:
  S:=X[1]+X[N];
  for k:=1 to N do
    for m:=1 to 2*N*N do
      X[k]:=X[k]+X[m]+S;
O(log N)
O(N)
O(N2)
O(N3)
O(2N)
9. Задан массив X[1..N]. Определите наиболее точную оценку временной сложности алгоритма:
  L:=1; 
  R:=N+1;
  while L<R-1 do begin
    c:=L+div(R-L,2)
    if R < X[c] then R:=c
    else             L:=c;
  end;
O(log N)
O(N)
O(N2)
O(N3)
O(2N)
10. Задан массив X[1..N]. Определите наиболее точную оценку временной сложности алгоритма:
  k:=0;
  for i:=1 to N do
    if X[i] = R then begin
      k:=i;
      break;
    end;
O(log N)
O(N)
O(N2)
O(N3)
O(2N)
11. Задан массив X[1..N]. Определите наиболее точную оценку временной сложности алгоритма:
  for i:=1 to N-1 do
    for j:=N-1 downto i do
      if A[j]>A[j+1] then 
        Swap(A[j], A[j+1]);
O(log N)
O(N)
O(N2)
O(N3)
O(2N)