Рассчитать время работы в системе обозначений Big-O

Question

1 int sum=0;
2 long start = System.currentTimeMillis();
3 for (int i = 1; i <= N; i++) {
4 for (int j = 1; j <= N; j++) {
5 sum=sum+1;}}
6 long stop = System.currentTimeMillis();
7 long elapsed = (long)(stop - start);

Я застрял в этом вопросе. Я знаю, что строки 1,2,5,6 and 7 являются примитивными операциями, которые они выполняют при O(1) постоянном времени.У меня есть сомнения по поводу циклов, я думаю, что это O(n^2) может кто-нибудь уточнить это спасибо.

Answer 1

Вот комментарий от Reddit, в котором приводятся хорошие примеры некоторых различных O.

ссылка

В этом сценарии учитель потерял свою ручку ипытается выяснить, кто из студентов взял его.

O (n2): Я спрашиваю студента и спрашиваю его: «У Джеффа есть ручка? Нет? У Боба есть ручка?»И так далее, называя каждого студента.Если я не получу ответ от первого ученика, я перейду к следующему.В худшем случае мне нужно задать n2 вопроса - опросить каждого учащегося о другом ученике.

O (n): Я спрашиваю каждого ученика, есть ли у него ручка.Если нет, я перехожу к следующему.В худшем случае мне нужно задать n вопросов.

O (log n): я делю класс на две части, а затем спрашиваю: «Это слева или справа от класса?»Затем я беру эту группу, делю ее на две части, спрашиваю снова и так далее.В худшем случае мне нужно задавать вопросы журнала n.

Я также должен добавить, что O (1) в основном задает всему классу: «У кого есть моя ручка?»Независимо от того, сколько человек в классе, вопрос о том, у кого есть ручка, займет столько же времени, и она станет постоянной.

Answer 2

Вы правы, один для одного цикла - это O (n), потому что время его работы линейно пропорционально размеру входа, и вместе со вторым циклом это O (n ^ 2), потому что вы повторяете O (n) функция n раз.