АлгЯзык: 17 - Сложность алгоритмов

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