Асимптотические среды выполнения InsertionSort и FingerTreeSort

Question

Я искал в своей книге все выше и ниже, а также несколько сайтов в Интернете, но я не совсем уверен в своих ответах.

Мне нужно дать асимптотическое время выполнения InsertionSort и FingerTreeSort (на основе RB-деревьев) в отношении количества имеющихся инверсий. InsertionSort выполняется за время O(n+INV), а FingerTreeSort выполняется за O(n+n*lg(INV/n+1). Мне нужно дать асимптотическое время выполнения для INV = 0, n, n^1.5 и n^2/. 4.

Я пришел к выводу, что InsertionSort работает в: O(n), O(n), O(n^2) и O (n ^ 2)

Это правильно? Почему бы и нет? (Я особенно не уверен насчет INV = n и n^1.5)

И для FingerTreeSort: O(n*lg(n)), O(n*lg(n)), O(n*lg(sqrt(n))) и O(n*lg(n^2))

Я сомневаюсь во всех из них в FingerTreeSort, но я думаю, что так и должно быть. Как мне найти правильную асимптотику? Например, для FingerTreeSort и n^1.5, я думаю, что он даст O(n+n*lg(n^1.5/n+1), подключившись к общему времени выполнения и упростив: O(n+n*lg) (sqrt(n)+1) и, учитывая его асимптотику, я могу игнорировать более низкие цифры, такие как +1 и + n, которые дают мне O(n*lg(sqrt(n))). Это правильный способ сделать это??

Заранее спасибо тем, кто ответит на этот вопрос. Я очень ценю это:)

пс. писать на языке Java, не то чтобы это имело значение для вопроса.

Answer 1

Сортировка вставки:
Формула: O (n + inv)
inv = 0: O (n)
inv = O (n): O (n + n) = O (n)
inv = O (n ^ 1.5): O (n + n ^ 1.5) = O (n ^ 1.5)
inv = (n ^ 2) / 4: O (n + n ^ 2) = O (n ^ 2)

FingerTreeSort:
Формула (используя форму, предоставленную OP): O (n + n * (ln [(inv / n) +1]))
inv = 0: O (n)
inv = O (n): O (n + n * (ln [(O (n) / n) + 1])) = O (n + n * (ln [O (1) +1]))) = O (п)
inv = O (n ^ 1.5): O (n + n * (ln [(O (n ^ 1.5) / n) + 1])) = O (n + n * (ln [c * (n ^ 0.5)) + 1])) =
O (n + 0,5 * n * ln (n)) = O (n * ln (n))
Аналогично, для inv = O (n ^ 2): O (n * ln (n))