Сложность сортировки по времени с альтернативной функцией слияния

Question

У меня сейчас есть этот код:

public static void main(String[] args) throws FileNotFoundException {
    Scanner sc = new Scanner(new File(args[0]));
    int amount = sc.nextInt();
    int[] array = new int[amount];

    for (int i = 0; i < amount; i++) {
        array[i] = sc.nextInt();
    }

    System.out.println("FINAL ANSWER " + find(array, 0, array.length - 1));
}


static int find(int arr[], int l, int r) {
    int answer = 0;
    if (l < r) {
        int m = (l + r) / 2;

        int a = find(arr, l, m);
        int b = find(arr, m + 1, r);

        answer = a + b + answer(arr, l, m, r);
    }
    return answer;
}


static int answer(int arr[], int l, int m, int r) {
    int ans = 0;
    for (int i = m; i < r; i++) {
        for (int j = l; j < m + 1; j++) {

            if (arr[i + 1] > arr[j]) {
                ans++;

            }
        }
    }

    return ans;
}

Я знаю, что сортировка слиянием имеет временную сложность O (nlog (n)) , однако я заменил функцию слияния функцией с двумя циклами for. Итак, теперь O (n ^ 2) , поскольку l, m и r зависят от n ?

Answer 1

Функция answer имеет сложность O( (r-m) * (m+1-l) ). Внешний for-l oop идет от m до r, то есть r-m итераций. Внутренний for-l oop изменяется от l до m+1, поэтому m+1-l итераций.

Учитывая наихудший случай l=0, r=n и m=n/2, функция может быть приблизительно к O(n^2).

Однако вам нужно добавить время выполнения функции find. Таким образом, общая временная сложность будет:

• O(n^2 * log(n)).