Асимптотический анализ с использованием основной теоремы на примере фиктивного объединения

Question

Предположим, что у нас есть фиктивная сортировка слияния, где операция слияния стоит O(n^2) вместо O(n). Тогда из основной теоремы, мы имеем:

T(n) <= aT(n/b) + O(n^d) 
T(n) <= 2T(n/2) + O(n^2) 

С a < b^d, мы находим, что:

T(n) = O(n^d) 
T(n) = O(n^2) 

Однако, интуитивно, он также имеет смысл, что большая O будет T(n) = O(n^2 logn), поскольку каждая рекурсия будет выполнять квадратный (n^2) поиск по номерам. Например, в случае линейного поиска сортировка слиянием равна O(n logn). Кто-нибудь знает, почему граница не O(n^2 logn)? Может ли это быть связано с тем, что поиск сокращается наполовину на каждой рекурсии?

Answer 1

Мы можем думать о времени, затрачиваемого для нормальной сортировки слиянием выглядит следующим образом (мы объединить 2 списки размера n/2, мы сливаемся 4 списки размера n/4, мы сливаемся 8 списков размера n/8 и т.д.):

2(n/2) + 4(n/4) + 8(n/8) + 16(n/16) + ... + n(1)

, который упрощает для:

n + n + n + ... + n = O(nlogn)

для вашего нового объединения рода мы имеем вместо этого:

2(n/2)^2 + 4(n/4)^2 + 8(n/8)^2 + 16(n/16)^2 + ... + n(1)^2

, который упрощает для:

n^2/2 + n^2/4 + n^2/8 + n^2/16 + ...

который затем становится:

n^2(1/2 + 1/4 + 1/8 + 1/16 + ...) = O(n^2)

Я надеюсь, что это обращается к своей интуиции.