Примечание BigO

Некоторые заметки о Big O

Большой О

O(1) Константа — без циклов

O(logN) Логарифмический — цикл по половине коллекции на основе условия и рекурсивный (пример: двоичный поиск)

O(n) Linear — нормальные циклы

O(n*log(n)) Лог-линейный — один цикл и цикл в половинной коллекции на основе условия и рекурсии. Пример: сортировка слиянием.

O(n²) Quadratic — Петля в петле

Две отдельные коллекции: O(a+b)

Одна коллекция, но два разных цикла: O(n)

Правило большого O

1. Всегда худший случай
2. Удалить константу

  public void test(a[]) {
    int a1 = a[0] -> O(1)
    a.forEach(element=>print(element)) -> O(n)
  }

Мы опускаем O(1) => эта функция имеет O(n)

3. Разные входы должны иметь разные переменные.

public void test(a[],b[]) {
  int a1 = a[0] -> O(1)
  a.forEach(element=>print(element)) -> O(a)
  b.forEach(element=>print(element)) -> O(b)
}

У нас разные входные данные => O(a+b)

И если у нас есть вложенный цикл с другим вводом => O (a * b)

4. Отбросьте недоминирующие термины.

public void test(a[],b[]) {
  int a1 = a[0] -> O(1)
  a.forEach(elementA=>print(elementA)) -> O(a)
  b.forEach(elementB=>{
      a.forEach(elementA=>print(elementA+elementB))
  }) -> O(a*b)
      
}

в этой функции, потому что наиболее доминирующим является вложенный цикл, поэтому эта функция имеет O (a * b)

Объясните BIG(O) на примере и математике

1. O(n²)

Пример: сортировка выбором

func selectionSort(a []int) {
   for i:=0;i< len(a);i++ {
      for j:=i+1;j<len(a);j++ {
         if a[j] < a[i] {
            a[j],a[i] = a[i],a[j];
         }
      }
   }
}

Предположим, у нас есть массив a = {4,5,3,2,6,1}

С вышеуказанной функцией. Числовое действие для каждой последовательности цикла

i = 0 -> j= 1: у нас есть 6 действий

i = 1 -> j = 2 : у нас есть 5 действий

i=5 -> j = 6 : у нас 0 действий

Таким образом, количество действий (или BigO) этой функции будет:

T(n) = 1+2+3 +4 ….+ (n-1) + n

Используя индуктивный метод, я пришел к выводу, что

T(n) = n(n+1)/2 = 1/2*n² + 1/2*n

Мы правим Big(O ) . Мы отбрасываем константу ( 1/2 ) и отбрасываем не доминирующий член ( n ) => T (n) = n² => Big (O) сортировки выбором равен O (n²)

2. О(логN)

Пример: бинарный поиск

func binarySearch(a []int,left int,right int,searchValue int) int {
   if(left==right) {
      return left;
   }
   mid := math.Floor(float64((right + left) / 2));
   if(searchValue < a[int(mid)]) {
      return binarySearch(a,left, int(mid)-1,searchValue);
   } else if(searchValue > a[int(mid)]){
      return binarySearch(a,int(mid)+1, right,searchValue);
   }
   return -1;
}

Предположим, у нас есть массив a = {1,2,3,4,5,6,7,8} и searchValue = 1.

С помощью вышеуказанной функции необходимо разделить массив на 3 три раза (это также 3 действия), пока мы не найдем searchValue с последовательностью середины

середина = 4 -> середина = 2 -> середина = 1

Я могу обобщить количество действий, необходимых для этого агортима, чтобы сформулировать

N/2^k =1 (n — общий элемент массива, а k — общее действие, которое нам нужно выполнить)

N/2^k =1 -> 2^k = N -> k = logN