Паскаль: 17 - Сложность алгоритмов

1. Задан массив X[1..N]. Определите число операций сложения, которые выполняются при работе этой программы:
  S:=X[1]+X[N];
  for k:=1 to N do begin
    X[k]:=X[k]+X[k]+S
  end;
Для обозначения операции умножения используйте символ *.
Ответ: 
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. Количество операций при выполнении некоторого алгоритма равно
  T(N) = 5*N2 + 3*N + 1
Определите наиболее точную оценку временной сложности алгоритма.
O(1)
O(N)
O(N2)
O(N3)
O(2N)
5. Количество операций при выполнении некоторого алгоритма равно
  T(N) = N3 - 3*N2 + N
Определите наиболее точную оценку временной сложности алгоритма.
O(1)
O(N)
O(N2)
O(N3)
O(2N)
6. Количество операций при выполнении двух алгоритмов для массива размером N таково:
  T1(N) = N2 - N - 10
  T2(N) = 4N + 40
Определите размер массива N, для которого время выполнения обоих алгоритмов одинаково.
Ответ: 
7. Задан массив X[1..N]. Определите наиболее точную оценку временной сложности алгоритма:
  S:=X[1]+X[N];
  for k:=1 to N do
    X[k]:=X[k]+S;
O(1)
O(N)
O(N2)
O(N3)
O(2N)
8. Задан массив X[1..N]. Определите наиболее точную оценку временной сложности алгоритма:
  S:=X[1]+X[N];
  for k:=1 to N do begin
    for m:=1 to 5 do begin 
      X[k]:=X[k]+S
    end
  end;
O(1)
O(N)
O(N2)
O(N3)
O(2N)
9. Задан массив X[1..N]. Определите наиболее точную оценку временной сложности алгоритма:
  S:=X[1]+X[N];
  for k:=1 to N do
    for m:=1 to N do
      for q:=1 to N do
        X[k]:=X[k]+X[q]+S;
O(1)
O(N)
O(N2)
O(N3)
O(2N)
10. Задан массив X[1..N]. Определите наиболее точную оценку временной сложности алгоритма:
  S:=X[1]+X[N];
  for k:=1 to N do
    for m:=2 to 2*N*N do begin
      X[k]:=X[k]+X[m]+S
    end;
O(1)
O(N)
O(N2)
O(N3)
O(2N)
11. Задан массив X[1..N]. Определите наиболее точную оценку временной сложности алгоритма:
  k:=0;
  for i:=1 to N do
    if X[i] = R then begin
      k:=i;
      break
    end;
O(1)
O(N)
O(N2)
O(N3)
O(2N)