Основна Суть Алгоритмів

Розглянемо задачу. Необхідно порахувати n-й член послідовності Фібоначчі. 1, 1, 2, 3, 5, 8, 13, 21, ...Кожний наступний член послідовності це сума двох попередніх.

Досить легко можна розв'язати задачу рекурсивним методом.

public static void main(String[] args) {
  int N = 6;
  System.out.println(fib(N));
}

public static int fib(int N) {
  if (N <= 2) return 1;
  return fib(N - 1) + fib(N - 2);
}
    

Це рішення дає правильний результат. Але що на рахунок швидкодії? Наскільки швидко працює наше рішення на різних значеннях N. Пропоную це заміряти.

public static void main(String[] args) {
  for (int N = 1; N <= 1000; N++) {
    long startTime = System.currentTimeMillis();
    fib(N);
    double time = (System.currentTimeMillis() - startTime) / 1000.0;
    System.out.printf("N: %3d, time: %.3f sec\n", N, time);
  }
}
    

результат

N:   1, time: 0.000 sec
N:   2, time: 0.000 sec
N:   3, time: 0.000 sec
N:   4, time: 0.000 sec
N:   5, time: 0.000 sec
N:   6, time: 0.000 sec
N:   7, time: 0.000 sec
N:   8, time: 0.000 sec
N:   9, time: 0.000 sec
N:  10, time: 0.000 sec
N:  11, time: 0.000 sec
N:  12, time: 0.000 sec
N:  13, time: 0.000 sec
N:  14, time: 0.000 sec
N:  15, time: 0.000 sec
N:  16, time: 0.000 sec
N:  17, time: 0.000 sec
N:  18, time: 0.000 sec
N:  19, time: 0.000 sec
N:  20, time: 0.000 sec
N:  21, time: 0.000 sec
N:  22, time: 0.000 sec
N:  23, time: 0.000 sec
N:  24, time: 0.000 sec
N:  25, time: 0.001 sec
N:  26, time: 0.000 sec
N:  27, time: 0.000 sec
N:  28, time: 0.001 sec
N:  29, time: 0.002 sec
N:  30, time: 0.002 sec
N:  31, time: 0.004 sec
N:  32, time: 0.006 sec
N:  33, time: 0.009 sec
N:  34, time: 0.015 sec
N:  35, time: 0.025 sec
N:  36, time: 0.042 sec
N:  37, time: 0.066 sec
N:  38, time: 0.106 sec
N:  39, time: 0.169 sec
N:  40, time: 0.306 sec
N:  41, time: 0.452 sec
N:  42, time: 0.694 sec
N:  43, time: 1.128 sec
N:  44, time: 1.853 sec
N:  45, time: 2.941 sec
N:  46, time: 4.876 sec
N:  47, time: 7.777 sec
N:  48, time: 12.564 sec
N:  49, time: 20.534 sec
N:  50, time: 32.771 sec
N:  51, time: 52.348 sec
    

Як бачимо час виконання для різних  N різний. І з кожним збільшенням на 1 час зростає не лінійно. Легко помітити, що зі значення N : 43 час збільшується в два рази з невеликою похибкою.

Ми можемо аналітично порахувати час для N : 100 за формулою


(N - 43) ^ 2
    

для N = 100


(100 - 43) ^ 2 = 3249 sec = 54 min
    

Чи можете ви вгадати приблизний час виконання програми для N = 200 не рахуючи? Тепер порахуємо.


(200 - 43) ^ 2 = 24649 sec = 410 min = 6.8 h
    

Нам би довго прийшлося чекати на результат :) А для 300?


(300 - 43) ^ 2 = 66049 sec = 1100 min = 18 h
    

А 1000?


(1000 - 43) ^ 2 = 915849 sec = 15264 min = 254 h = 10 days
    

Для N = 100 000 час виконання 316 років. Скоріш за все ми не дочекаємось результату за час нашого життя.

А що робити, коли нам він треба? І не через роки, а прямо зараз.

Задача з числами Фібоначчі трохи надумана. В ній немає практичної користі. Але існує маса реальних задач де час росте дуже швидко і це критично важливо.

В цьому місці і починаються алгоритми.

Алгоритм - це підхід, що на порядки зменшує час виконання програми чи об'єм використовуваних ресурсів. Тож як ми могли вирішити цю задачу інакше?

Наприклад так:

public static int fib(int N) {
  int result = 1;
  int previous = 1;

  for (int N = 1; N <= 1000; N++) {
    int next = result + previous;
    previous = result;
    result = next;
  }
  return result;
}
    

І час завжди буде менше секунди для будь-якого значень N. Для першого способу час зростав експоненціально, а для другого лінійно. Заведено казати - складність алгоритму експоненціальна О(2^N) і складність алгоритму лінійна О(N). Відповідно всі рішення діляться по класах складності

O(1) константна
O(log N) логарифмічна
O(N) лінійна
O(N * log N)
----------------------- все що нижче працює "повільно".
O(N^2) квадратична
O(N^3)
O(2^N) експоненціальна
O(N^N) поліноміальна
    

Якщо ви хочете розібратися в алгоритмах, перший крок - треба навчитися визначати складність рішення.

Наступний крок - розібрати ряд стандартних підходів(алгоритмів) класичних задач, щоб понизити порядок складності програми.

Тепер, я думаю, стає очевидним в чому суть алгоритмів і для чого вони потрібні.