Python: 11 - Сложность вычислений

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