Анализ Algothm bigO и нормальная запись

Question

int I(int i, int j, int n) 
{ 
   return n * i + j;                                    >1
}
int DotProduct( int A[], int B[], int i, int j, int n )
{
   int t=0;                                             >1
   for(int k=0; k<n; k++ )                              > n+1              
      t += A[ I(i,k,n) ] * B[ I(k,j,n) ];               > n
   return t;                                            > n 
}
void MMultiply( int A[], int B[], int C[], int n ) 
{
   for( int i=0; i<n; i++ )                          > n+1
      for( int j=0; j<n; j++ )                       > (n)n+1
         C[ I(i,j,n) ] = DotProduct(A, B, i, j, n );  > see function above (n)(n)(3n+2)?
}

я не уверен, должен ли я публиковать на старом или новом посте, так что пост на новом только потому, что это срочно (учится на среднесрочный период)

В любом случае, я знаю большоеO это n ^ 3

(3n + 2) (n) (n) + (n + 1) (n) + (n + 1) <сделал ли я это правильно? </p>

Я ненавижу, когда учитель учит чему-то, чего нет в книге!

Answer 1

Вы начинаете с самого начала: сначала вам нужно рассчитать время, необходимое для запуска среднего случая MMultiply:

Первое, что вы можете увидеть в MMultiply, это цикл от 0 до n - 1, который дает вам:

T (MMultiply) = n * (T (what_is_inside_the_first_loop))

Теперь вам нужен T (what_is_inside_the_first_loop). Поскольку у вас есть только другой цикл внутри первого цикла, T (what_is_inside_the_first_loop) = n * T (what_is_inside_the_second_loop)

Внутри второго цикла находится только один вызов «DotProduct», поэтому, игнорируя назначение «=», T (what_is_inside_the_second_loop) = T (DotProduct).

Чтобы вычислить T (DotProduct), вы берете функцию построчно:

• 1 для начального назначения
• n для цикла
• 3 для каждой итерации цикла (1 для операции «+ =» и 1 для каждого вызова I, который выполняет только одну операцию)

т. Д. (DotProduct) = 1 + n * 3

замена T (DotProduct) в начальном ecuation дает вам:

T (MMultiply) = n * n * (1 + n * 3) = 3 * n ^ 3 + n ^ 2

так

T (MMultiply) = 3 * n ^ 3 + n ^ 2

нотация большого О в основном просто назначает это время определенному классу (это приближение). Класс, который лучше всего соответствует «3 * n ^ 3 + n ^ 2», равен n ^ 3 (поскольку n ^ 3 является наиболее значимым членом). Так что T (MMultiply) = O (n ^ 3).

Ваши вычисления были почти правильными, но у вас было положительное сальдо "+ 1" в первых двух строках MMultiply и, если вы прокомментировали для каждой строки время, необходимое для обработки этой строки, "t + = A [I ( i, k, n)] * B [I (k, j, n)]; "не принимает n, требуется только 2. То же самое касается" return t ", требуется только 1.

Answer 2

простой подход:

• количество вложенных циклов: N^3
• количество операций: 2 (+, *)
• всего равно 2N^3