Почему O (2 ^ n) отличается от O (2 ^ (n / 2))?

Question

Рассмотрим следующую проблему из книги, которая пытается объяснить технику "встретиться посередине" - https://cses.fi/book/book.pdf (стр. 54, PDF p64)

В качестве примера рассмотрим проблему, в которой нам дан список из n чисел и числа x, и мы хотим выяснить, возможно ли выбрать несколько чисел из списка, чтобы их сумма была равна x. Например, учитывая список [2,4,5,9] и x = 15, мы можем выбрать числа [2,4,9], чтобы получить 2 + 4 + 9 = 15. Однако, если x = 10 для тот же список, невозможно сформировать сумму.

...

Простой алгоритм задачи состоит в том, чтобы пройти через все подмножества элементов и проверить, равна ли сумма любого из подмножеств x. Время выполнения такого алгоритма составляет O (2 ⁿ ), потому что есть 2 ⁿ подмножеств. Однако, используя технику встреч в середине, мы можем добиться более эффективного алгоритма времени O (2 ^{n / 2} ). Обратите внимание, что O (2 ⁿ ) и O (2 ^{n / 2} ) являются различными сложностями, потому что 2 ^{n / 2} равно √2 ^ n.

1. Они квадратные корни времени Big Oh, разделив подмножество. Но почему именно это все равно отличается от оригинала 2 ⁿ ?

2. Скажите, что эти два раза разные. Разве эта разница настолько значительна?

3. Вместо того, чтобы просто делить пополам набор, почему бы им не вернуться рекурсивно к базовому случаю, когда у вас есть только один набор элементов и 2 ^ 1 подмножества (как в сортировке слиянием)? Разве это не повысит эффективность, если вы сложите их вместе?

PS: я знаю, что эта книга - плохой справочник по C ++, но я использую ее для объяснения алгоритма.

Answer 1

Предположим, что они будут одинаковыми.Тогда вы могли бы сказать, что 2 ⁿ = O (2 ^{n / 2} ) .Это означает, что есть некоторые c> 0 и n ', такие что для всех n> n' ,

2 ⁿ n / 2 .

Деление обеих сторон эквивалентно тому, что для всех n> n ',

2 ^{n / 2} .

Это, очевидно, невозможно, поскольку левая сторона уходит в бесконечность с достаточно большими n , поэтому он не ограничен никакими c .