Ответ 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). График времени будет выглядеть так:
Примечание. До 7 элементов f (x) выполняется быстрее, хотя это O (n ^ 2).
Для 8 или более элементов g (x) выполняется быстрее.
Пример 2
Бинарный поиск - O (log n), идеальная хэш-таблица (без столкновений) - это O (1), но, верьте мне, хэш-таблица не всегда всегда быстрее, чем бинарный поиск в действительности. Используя хорошую хэш-функцию, хеширование строки может занять больше времени, чем это делает весь бинарный поиск. С другой стороны, использование плохой хеш-функции создает много коллизий, и чем больше коллизий означает, что ваш поиск в хэш-таблице не будет действительно O (1), потому что большинство хеш-таблиц разрешают столкновения таким образом, чтобы они выполняли поиск либо O (log2 n), либо даже O (n).