Асимптотические временные интервалы 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

что я придумал сам с собой, что сортировка вставками работает в: О (п), 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))

У меня есть сомнения по поводу всех из них в FingerTre eSort, но я думаю, что они должны быть. Как найти правильное асимптотическое время выполнения? Например, для 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))). Это правильный способ сделать ? это

заранее спасибо тем, что ответить на этот вопрос, я сильно appriciate его :)

пс писать в Java, не так уж важно, чтобы вопрос

Answer 1

вставки Сортировать:...
Formul а: О (п + INV)
INV = 0: О (п)
INV = О (п): О (п + п) = О (п)
INV = O (N^1.5): О (п + п^1,5) = О (п^1,5)
инв = (п^2)/4: О (п + п^2) = O (N^2)

FingerTreeSort:
Формула (используя один поставляемый OP): O (п + п * (пер [(INV/п) + 1]))
inv = 0: O (n)
inv = O (n): O (n + n * (ln [(O (n)/n) + 1])) = O (n + n * (ln [O (1) +1])) = O (n)
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))