Как рассчитать Big O для этого алгоритма?

Question

Я хочу найти Big O метода1.

public static void method1(int[] array, int n) 
{ 
    for (int index = 0; index < n - 1; index++) 
    { 
     int mark = privateMethod1(array, index, n - 1); 
     int temp = array[index]; 
     array[index] = array[mark]; 
     array[mark] = temp; 
    } // end for 
} // end method1 

public static int privateMethod1(int[] array, int first, int last) 
{ 
    int min = array[first]; 
    int indexOfMin = first; 
    for (int index = first + 1; index <= last; index++) 
    { 
     if (array[index] < min) 
     { 
      min = array[index]; 
      indexOfMin = index; 
     } // end if 
    } // end for 
    return indexOfMin; 
} // end privateMethod1 

Мое мышление заключается в том, что нам не нужно заботиться о privateMethod1, это правда? Не нужно ли беспокоиться о вызовах функций при вычислении Big O и просто учитывать другие факторы, такие как операции присваивания в нашем методе1?

Спасибо.

Answer 1

Только операции, выполняемые в постоянное время, O(1), можно рассматривать как основные операции в вашем анализе времени работы вашего алгоритма; в этом конкретном случае находим верхнюю асимптотическую оценку для вашего алгоритма (обозначение Big-O). Количество итераций в петле for вашего метода privateMethod1 зависит от index от method1 (что само зависит от n), а также от n и явно не работает в постоянное время.

Следовательно, мы должны включить privateMethod1 в наш анализ вашего алгоритма Big-O. Мы будем рассматривать все другие операции, такие как присвоения, и операторы if в качестве основных операций.

Обработанные в качестве основных операций в нашем анализе:

/* in 'method1' */ 
int temp = array[index]; 
array[index] = array[mark]; 
array[mark] = temp; 

/* in 'privateMethod1' */ 
int min = array[first]; 
int indexOfMin = first; 

//... 

if (array[index] < min) 
{ 
    min = array[index]; 
    indexOfMin = index; 
} 

---

С этим прояснилось, вы можете проанализировать алгоритм, используя Sigma обозначения: внешняя сумма описывает петлю for в method1, а внутренний цикл описывает цикл for в privateMethod1, а 1 обобщает «стоимость» всех основных операций во внутреннем цикле for.

Следовательно, верхняя асимптотическая граница для вашего алгоритма method1 является O(n^2).

Answer 2

Мое мышление заключается в том, что нам не нужно заботиться о privateMethod1, это правда?

Нет, вы ошибаетесь. Вы должны заботиться о других вызовах функций при вычислении сложности. privateMethod1 работает в O(n) раз, так как в худшем случае fist будет 0 и last всегда n - 1. Таким образом, ваша общая петля, то есть method1, работает в O(n^2) времени.