私は自分の本やインターネット上のいくつかのサイトをよく調べましたが、自分の答えについて完全には確信が持てません.
存在する反転の数に関して、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 (sqrt(n)+1) であり、漸近的であるため、+1 や +n などの下位の数値を無視して O(n*lg(sqrt(n))) を得ることができます。これは正しい方法ですか? ?
この質問に答えてくださった方々に、あらかじめ感謝いたします。私はそれを大いに感謝します:)
ps。Javaで書いていますが、質問には関係ありません。