Q02.11. Examples of algorithms classes of complexity (Big-O nonation)

[glbter]

Q02.11. Приклади алгоритмів з різними класами складності (big-O)

• Наведіть приклади алгоритмів з різними класами складності - і часу, і простору Наприклад, O (1), O (log n), O (n), O (n log n),…
• Додаткові бали за незвичайні оцінки складності

Q02.11. Examples of classes of algorithms (Big-O notation)

• Provide different examples of algorithms with different classes of complexity - time and memory. For example, O (1), O (log n), O (n), O (n log n),…
• You can get bonuses for unusual complexity grades

[glbter]

Стандартні класси

• O(1)
  • RAM
  • доступ по хешу
• O(log n)
  • бінарний пошук у відсортованих масивах або збалансованих бінарних деревах
  • операції у цих деревах та біноміальних купах.
  • Взагалі притаманний поділу проблеми на 2.
  • До речі, найшвидша оцінка алгоритму сортування, що базується на порівнянні.
  • FFT обрахунок дискретного перетворення Фур'є, що використовується в обробці сигналів (розклад за амплітудами, частотами)
• O(n)
  • повний обхід структури,
  • пошук у невідсортованому масиві або списку,
  • пошук у не сбалансованому дереві.
  • Сортування без порівнянь, наприклад Counting search
• O(n^2)
  • повний обхід усіх пар елементів,
  • деякі алгоритми сортування (побудовані на цьому принипі) Bubble Sort і тд.
  • Верхня межа для більш швидких алгортмів Quick Sort, Shell Sort
• O(n^3)
  • обхід усіх трійок елементів
• O(c^n), where c = Const > 1
  • розв'язок задачі мандрівника з використанням динамічного програмування
• O(n!) (sometimes n^n)
  • нумерація усіх можливих перетинів множини
  • на попередньому принципі базується нижня оцінка для таких речей як Random Sort, Monkey Sort, BogoSort.
  • розв'язок задачі мандрівника методом грубої сили

Деякі цікаві оцінки

• O(log(log(n)))
  • Interpolation search пошук у відсортованих масивах з рівномірно розподіленими даними. Досить простий алгоритм, окрім формули розрахунку. Алгоритм нагадує двійковий пошук.
• O(n^(0.5))
  • Jump search пошук у відсортованих масивах але замість кроку в 1 елемент, використовується крок в n^(0.5) елементів.
• O((log(n))^c), where c = Const > 1
  • паралельний RAM
• O(n^c), where c = Const, 0 < c < 1
  • пошук у k-d дереві ( дерево для зображення точок у k-вимірному просторі)k-d дерево, lecture, implementation
• O(log* n) (log-star)
  • в цілому це велика кількість логарифмів, у використанні Union Find, для покращення елемент у дереві піднімаєься на рівень вище, у результаті теоретично можна отримати корінь і n дітей. Тобто O(log* n) ~ O(1)

[glbter]

[ZinchenkoArtem1]

• O(1) Визначенно парності числа (у двійковому запису)
• O(log* n) Розподілені розфарбовування циклів
• O(log log n) Час амортизації на одну операцію при використанні обмеженої черги з пріоритетом
• O(n) Пошук найбільшого або найменшого елементу невпорядкованого масиву
• O(n log n) Найшвидше можливе сортування порівняннями; Швидке перетворення Фур'є.
• O(n3) Безпосереднє множення двох матриць розміру n×n. Обчислення часткової кореляції.
• 2^(O(n)) Вирішення задачі комівояжера за допомогою динамічного програмування
• O(n!) Вирішення задачі комівояжера повним перебором

[BohdanKasiudyk]

можливо трішки не в тему ось посилання на обговорення цыкавоъ для мене теми про neural network:https://stackoverflow.com/questions/53843459/neural-networks-and-big-o