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

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