The time complexity of the number of comparisons in half insertion sort

[]The time complexity of the number of comparisons in [half insertion sort]

Half-fold insertion sort — the number of comparisons when inserting the Nth number. [Time complexity] O(nlog2(n)):

According to the algorithm idea, there are the following inferences:

Each number is inserted into the [depth]
of a decision tree at most , i.e. log2(n-1) (take the least positive integer) + 1

Analysis: Each comparison of the number inserted in the [ordered array] is compared with the number pointed to by Mid (Mid points to the middle position in the array to be compared). First, convert the ordered array into a binary tree form similar to a decision tree. The number of comparisons can only be up to the depth of this binary tree.

Example:

Suppose a set of ordered arrays: 1 2 3 4 5 6 7 8 9 (note that the already selected Mid will not be reselected)

First Mid:
low=1, high=9, so Mid=(low+high)/2=5
        Build the root of the binary tree
             ⑤

Second Mid:
On the left of 5 low=1 high=4 Mid=(low+high)/2=2
On the right of 5 low=6 high=9 Mid=(low+high)/2=7
         Continue to expand the binary tree
             ⑤
          ②     ⑦

Third Mid:
On the left of 2 low=1 high=1 Mid=(low+high)/2=1
On the right of 2 low=3 high=4 Mid=(low+high)/2=3
On the left of 7 low=6 high=6 Mid=(low+high)/2=6
On the right of 7 low=8 high=9 Mid=(low+high)/2=8
         Continue to expand the binary tree
             ⑤
        ②         ⑦
    ①     ③    ⑥      ⑧

Fourth Mid:
On the right of 3 low=4 high=4 Mid=(low+high)/2=4
On the right of 8 low=9 high=9 Mid=(low+high)/2=9
        Continue to expand the binary tree
            ⑤
     ②            ⑦
  ①     ③      ⑥     ⑧
          ④            ⑨

Until all elements of the sorted array are present, the conversion is completed
(any sorted array can be converted into a binary tree in this way)

When inserting a 10: (the comparison is completed when there is no number to compare with it, the small left is the big right)
         ⑤ (Compare with 5 for the first time, and then compare the right side of 5 if it is greater than 5)
    ② ⑦ (Compare with 7 for the second time, and then compare the right side of 7 if it is greater than 7)
  ① ③ ⑥ ⑧ (comparison with 8 for the third time, and then compare the right side of 8 if it is greater than 8)
       ④ ⑨ (Compare with 9 for the fourth time. If it is greater than 9, then compare the right side of 9. If 9 has no right child, there is no need to compare it again. The comparison is complete)

The number of comparisons is 4
According to the formula, log2(10-1) (take the least positive integer)+1=3+1=4

It can be seen that when inserting the Nth number into an ordered [array] , there are already N-1 numbers in the ordered array, and the number of comparisons can only be up to N-1 numbers that already exist in the ordered array . The depth of the binary tree into which 1 number is converted.
That is, log2(N-1) (take the least positive integer) + 1

The depth of a complete binary tree with n nodes is “log2n”+1

So the number of comparisons N < =log2(n-1) (take the least positive integer)+1 
      n-1 
let i = n, ∑ = log2(1)+1+log2(2)+1+....+log2 (n-1)+1 
      i = 1 
= log2[(n-1)! ]+n log2 [( n-1 ) 
when n is large ! ]≈ log2 ( n !)
In the computer for the convenience of calculating log2 ( n !) ≈ n * log2 ( n )
 log2 ( n !) is the same order of magnitude as n * log2 ( n )

The total time complexity of the number of comparisons available is O(nlog2(n))

The first time I write an article, it may not be correct. If there is any error, please point out, and my brother must change it.

Leave a Comment

Your email address will not be published. Required fields are marked *