Сложность времени (Java, Quicksort)

Question

У меня есть очень общий вопрос о вычислении временной сложности (нотация Big O). когда люди говорят, что худшая временная сложность для QuickSort - это O (n^2) (выбор первого элемента массива как точки поворота каждый раз, а массив отсортирован обратно), с какой операцией они учитывают, чтобы получить O (n^2)? Считают ли люди сравнения, сделанные утверждениями if/else? Или они рассчитывают только общее количество свопов? Как правило, как вы знаете, какие «этапы» рассчитывать для вычисления нотации Big O.

Я знаю, что это очень простой вопрос, но я прочитал почти все статьи о Google, но до сих пор не понял его

Answer 1

Худшие случаи быстрой сортировки
Наихудший Быстрого сортировки когда массив отсортирован в обратном порядке, сортируется нормально и все элементы равны.

---

Понимать Big-Oh
Сказав это, давайте сначала понять, что означает Big-О чем-то.

Когда мы имеем только и асимптотическую верхнюю границу, мы используем O-нотацию. Для данной функции g (n) обозначим через O (g (n)) множество функций, O (g (n)) = {f (n): существуют положительные c и n _o,
такие, что 0 < = е (п) < = CG (п) для всех п> = п _о}

---

Как рассчитать Big-Oh?
Big-Oh в основном означает, что сложность программы возрастает с размером ввода.

Вот код:

import java.util.*; 
class QuickSort 
{ 
    static int partition(int A[],int p,int r) 
    { 
     int x = A[r]; 
     int i=p-1; 
     for(int j=p;j<=r-1;j++) 
     { 
      if(A[j]<=x) 
      { 
       i++; 
       int t = A[i]; 
       A[i] = A[j]; 
       A[j] = t; 
      } 
     } 

     int temp = A[i+1]; 
     A[i+1] = A[r]; 
     A[r] = temp; 
     return i+1; 
    } 
    static void quickSort(int A[],int p,int r) 
    { 
     if(p<r) 
     { 
      int q = partition(A,p,r); 
      quickSort(A,p,q-1); 
      quickSort(A,q+1,r); 
     } 
    } 
    public static void main(String[] args) { 
     int A[] = {5,9,2,7,6,3,8,4,1,0}; 
     quickSort(A,0,9); 
     Arrays.stream(A).forEach(System.out::println); 
    } 
} 

Примите во внимание следующие утверждения:

Блок 1:

int x = A[r]; 
int i=p-1; 

Блок 2:

if(A[j]<=x) 
{ 
    i++; 
    int t = A[i]; 
    A[i] = A[j]; 
    A[j] = t; 
} 

Блок 3:

int temp = A[i+1]; 
A[i+1] = A[r]; 
A[r] = temp; 
return i+1; 

Блок 4:

if(p<r) 
{ 
    int q = partition(A,p,r); 
    quickSort(A,p,q-1); 
    quickSort(A,q+1,r); 
} 

Предполагая, что каждый операторы принимают постоянное время с. Давайте вычислим, сколько раз вычисляется каждый блок.

Первый блок выполнен 2c раз. Выполняется второй блок 5c раз. Блок жажды выполнен 4c раз.

Мы пишем это как O (1), что подразумевает, что количество операторов времени выполняется столько же раз, даже когда размер ввода меняется. все 2c, 5c и 4c все O (1).

Но, когда мы добавим петлю на втором блоке

for(int j=p;j<=r-1;j++) 
{ 
    if(A[j]<=x) 
    { 
     i++; 
     int t = A[i]; 
     A[i] = A[j]; 
     A[j] = t; 
    } 
} 

Он работает в п раз (при условии, рп равно п, размер входных данных), то есть, НИКАКОЙ (1) раз, то есть, На). Но это не выполняется каждый раз каждый раз. Следовательно, мы имеем средний случай O (log n) i.e, пройдены по крайней мере log (n) элементы.

Теперь мы установили, что разбиение выполняется на O (n) или O (log n). Последний блок, который является методом quickSort, определенно работает в O (n). Мы можем рассматривать это как замкнутый цикл, который работает n раз. Следовательно, вся сложность - либо O (n), либо O (nlog n).

Answer 2

Рассчитано в основном на размер (n), который может расти, поэтому для быстрой сортировки массива это размер массива. Сколько раз вам нужно получить доступ к каждому элементу массива? если вам нужно только получить доступ к каждому элементу один раз, то это O (n) и т. д.

Будут учитываться переменные переменных/локальные переменные, которые растут с ростом n. Другие переменные, которые не растут значительно, когда n растет, можно считать постоянными: O (n) + c = O (n)

Answer 3

Просто чтобы добавить к сказанному, я согласен с теми, кто сказал, что вы считаете все , но если я правильно помню из своих классов алгоритмов в колледже, то накладные расходы подкачки обычно минимальны по сравнению со временами сравнения, а в некоторых случаях - 0 (если этот список уже отсортирован).

Например. формула для линейного поиска является

Т = К * Н/2.

где Т представляет собой общее время; K - некоторая константа, определяющая общее время вычисления; и N - количество элементов в списке.

В среднем число сравнений - N/2.

но мы можем переписать в следующем:

Т = (К/2) * N

или переопределение K,

Т = К * N.

Это делает ясно, что время прямо пропорционально размеру N, что нас действительно волнует. По мере того, как N значительно увеличивается, это становится единственной вещью, которая действительно имеет значение.

Бинарный поиск, с другой стороны, логарифмически растет (O log (N)).