PA обозначений Big O - PullRequest
Новая
       4

PA обозначений Big O

0 голосов
/ 19 сентября 2019

с учетом следующего цикла: 

while(int i = 0; i <= 10; i++) {
  System.out.println();
}

Это большой o(n) или o(1) ??Что заставляет меня думать, что это o(1) находится в логическом выражении, которое мы написали i <= 10, а не i <= n Или мне не нужно заботиться об этой детали?

1 Ответ

0 голосов
/ 20 сентября 2019

Когда мы говорим, что простой цикл for имеет временную сложность O (N), мы имеем в виду, что время, необходимое для выполнения цикла, зависит от размера ввода N. Например, 

function doLoop(n) {
     let i = 0;
     while (i < n) {
         console.log('doing stuff');
         i++;
     }

В этой функции, если мы передадим 2, наш цикл будет выполнен дважды, а если мы передадим 100, он будет выполнен 100 раз и т. Д.

В вашем цикле - мы вообще не пропускаем никакого ввода.Цикл ВСЕГДА будет выполняться ровно 10 раз.Таким образом, его O (10).Как правило, при выражении обозначения Big O мы игнорируем постоянные значения, и так как O (10) => 10 * O (1);Ваш цикл for равен O (1), постоянному циклу времени, который не зависит от размера любых входных переменных.

...