I took the merge sort, I need to calculate the complexity of the number of iterations, but for some reason I do not match. For example, for an array of length 16, the number of iterations should be 64. Tell me what and where is the error?

import java.io.File; import java.io.FileNotFoundException; import java.util.Scanner; public class M { private static int[] aux;//Π²ΡΠΏΠΎΠΌΠΎΠ³Π°Ρ‚Π΅Π»ΡŒΠ½Ρ‹ΠΉ массив для слияний public static long kol = 0; public static void sort(int [] a) { aux = new int [a.length]; sort(a, 0, a.length - 1); } private static void sort(int [] a, int lo, int hi) { kol++; if (hi <= lo) { return; } int mid = lo + (hi - lo) / 2; sort(a, lo, mid);//сортировка Π»Π΅Π²ΠΎΠΉ ΠΏΠΎΠ»ΠΎΠ²ΠΈΠ½Ρ‹ sort(a, mid + 1, hi);//сортировка ΠΏΡ€Π°Π²ΠΎΠΉ ΠΏΠΎΠ»ΠΎΠ²ΠΈΠ½Ρ‹ merge(a, lo, mid, hi);//слияниС Ρ€Π΅Π·ΡƒΠ»ΡŒΡ‚Π°Ρ‚ΠΎΠ² } public static void merge(int[] a, int lo, int mid, int hi) { int i = lo, j = mid + 1; for (int k = 0; k <= hi; k++) {//ΠΊΠΎΠΏΠΈΡ€ΠΎΠ²Π°Π½ΠΈΠ΅ a[lo..hi] Π² aux[lo..hi] aux[k] = a[k]; kol++; } for (int k = lo; k <= hi; k++) {//слияниС Π½Π°Π·Π°Π΄ Π² a[lo.. hi] kol++; if (i > mid) { a[k] = aux[j++]; } else if (j > hi) { a[k] = aux[i++]; } else if (aux[j]<(aux[i]) ) { a[k] = aux[j++]; } else { a[k] = aux[i++]; } } } public static void main(String... args) throws FileNotFoundException { int[] p = new int [16]; for (int i = 0; i < 16; i++) { p[i] = 10 - i; } sort(p); System.out.println(kol); for (int i = 0; i < 16; i++) { System.out.println(p[i]); } } }

    2 answers 2

    • What is the iteration in your presentation? Roughly speaking, can you precisely formulate the problem you are solving?

    As I understand it, you got 64, substituting your N in the formula ? = N log2 N ? = N log2 N That is, informally speaking, you calculated the number of constant operations that are required to complete the work of the MERGESORT, algorithm MERGESORT, for which, in turn, the algorithmic complexity Θ(N log N) known).

    • If this is an iteration in your view, then calculating their total number is not difficult. The MERGESORT algorithm works as follows:

       def MERGESORT: MERGESORT(LOW) MERGESORT(HIGH) MERGE(LOW, HIGH)

    • The running time of MERGESORT can be expressed as T(N) = 2 * T(N / 2) + N , since it is started recursively for the two halves of the sequence, and after that for N operations it performs their merging.

    • In order to calculate the number of these very operations (or iterations in your formulation), then you need to increase the total number of TOTAL operations by K for each MERGE call, where K is the total size of the LOW and HIGH, sequences received at the MERGE(LOW, HIGH) input MERGE(LOW, HIGH) .

    • In connection with the above, it is not very clear why you increase kol in three different places and what you were actually guided by when you decided to do it :)
    • @ Kotyk_hochet_kusat, IMHO TC simply counts the number of shipments (and doesn’t pay attention to comparisons) for iterations, because at each step of both cycles (each iteration ) one item is shipped. - avp

    In my here

      private static void sort(int [] a, int lo, int hi) { kol++; ....

    odd counting

    In general, mergesort has a little trick. In aux you can only copy lo half. And space under aux[] in this case, you only need a.length / 2 + 1 . This is true because before merge you yourself always divide the array in half.

    For some reason (maybe because of the paradigm of writing as universal functions as possible?) This is not mentioned in popular educational literature.

    Then merge into the result (the youngest of the aux, the youngest of the hi half).

    I hope it is clear.

    Update

    Something I wondered which half is better to copy (dealt somehow with this issue). I looked at myself and found that everything is correct, copy the first one ( lo, mid ).