Сложность времени для двух циклов

Итак, я знаю, что временная сложность:

for(i;i<x;i++){
   for(y;y<x;y++){
      //code
   }
}

есть n ^ 2

но будет:

for(i;i<x;i++){
   //code
}
for(y;y<x;y++){
   //code
}

be n + n?

Ответы

Ответ 1

Поскольку примечание Big-O не о сравнении абсолютной сложности, а только относительном, O (n + n) на самом деле совпадает с O (n). Каждый раз, когда вы удваиваете x, ваш код будет в два раза длиннее, чем раньше, а это означает O (n). Независимо от того, проходит ли ваш код через 2, 4 или 20 циклов, поскольку любое время, затрачиваемое на 100 элементов, потребуется в два раза больше времени для 200 элементов и в 100 раз больше времени для 10 000 элементов, независимо от того, сколько времени из которых расходуется внутри цикла.

Вот почему big-O ничего не говорит о абсолютной скорости. Тот, кто предполагает, что функция O (n ^ 2) f() всегда медленнее функции O (log n) g(), неверна. В нотации "большой О" только сказано, что если вы продолжаете увеличивать n, будет точка, в которой g() будет обгонять f() по скорости, однако, если n всегда остается ниже этой точки на практике, тогда f() может всегда будет быстрее, чем g() в реальном программном коде.

Пример 1
Пусть предполагается, что f (x) принимает 5 мс для одного элемента, а g (x) принимает 100 мс для одного элемента, но f (x) - O (n ^ 2), g (x) - O (log2 n). График времени будет выглядеть так:

enter image description here
Примечание. До 7 элементов f (x) выполняется быстрее, хотя это O (n ^ 2).
Для 8 или более элементов g (x) выполняется быстрее.

Пример 2
Бинарный поиск - O (log n), идеальная хэш-таблица (без столкновений) - это O (1), но, верьте мне, хэш-таблица не всегда всегда быстрее, чем бинарный поиск в действительности. Используя хорошую хэш-функцию, хеширование строки может занять больше времени, чем это делает весь бинарный поиск. С другой стороны, использование плохой хеш-функции создает много коллизий, и чем больше коллизий означает, что ваш поиск в хэш-таблице не будет действительно O (1), потому что большинство хеш-таблиц разрешают столкновения таким образом, чтобы они выполняли поиск либо O (log2 n), либо даже O (n).

Ответ 2

Это было бы 2n, так что да, вы правы.

Он обычно просто выражается как O (n), хотя, видя, что он линейный, а не квадратичный.

Конечно, он зависит от того, какой код находится внутри циклов, но, я думаю, вы уже это знаете.