Ефективність алгоритмів за часом виконання та простором пам'яті

Концепції комп'ютерних наук

Pritesh Patel

Computer Scientist & Data Scientist for over 20 years

Вступ до нотації Big-O

  • Вимірює зростання часу й пам'яті зі збільшенням вхідних даних
  • Приклади: $O(n)$, $O(n^2)$, $O(log\, n)$
  • «O» означає «порядок» зростання, напр., O(n) = лінійний
Концепції комп'ютерних наук

Складність за часом — офісна аналогія

Діаграма, що показує різні складності в нотації Big O

  • $O(1)$ — стала тривалість — «швидкий погляд» — «стала»
  • $O(log\,n)$ — повільне зростання часу — «поділ стопки» — «логарифмічна»
  • $O(n)$ — лінійне зростання — «читання документа» — «лінійна»
  • $O(n\,log\,n)$ — швидше зростання — «сортування стопки» — «лініарифмічна»
  • $O(n^2)$ — квадратичне зростання часу — «порівняння документів» — «квадратична»
Концепції комп'ютерних наук

Складність за простором — офісна аналогія

Діаграма, що показує різні складності в нотації Big O

  • $O(1)$ — сталий обсяг пам'яті — «місце на столі» — «стала»
  • $O(log\,n)$ — повільне зростання пам'яті — «мінімальні нотатки» — «логарифмічна»
  • $O(n)$ — лінійне зростання — «стікери» — «лінійна»
  • $O(n\,log\,n)$ — швидше зростання пам'яті — «тимчасові стопки» — «лініарифмічна»
  • $O(n^2)$ — квадратичне зростання пам'яті — «решітка порівнянь» — «квадратична»
Концепції комп'ютерних наук

Давайте потренуємось!

Концепції комп'ютерних наук

Preparing Video For Download...