Как найти асимтотическое время выполнения этого метода?

Меня попросили написать этот метод, а затем дать асимптотическое время выполнения с точки зрения размера массива. Может ли кто-нибудь объяснить мне, как это делается?

public int doSomething(int[] nums) {
    int count = 0;

    for (int i = 0; i < nums.length; i++)
        for (int j = 0; j < i; j++)
            if (nums[i] > nums[j])
                count++;

    return count;
}
Источник

2 ответа

Решение

Размер задачи N - это длина чисел.

Способ определить асимптотическое время выполнения из кода, где есть только операторы for, довольно прост.

Асимптотические времена выполнения описываются традиционными обозначениями, такими как

O(N)

Который является одним простым для утверждения. Нам нужно обработать входные элементы только один раз.

Вложенные операторы for, как у вас, означают, что нам нужно проверять значение каждого числа более одного раза.

Вы повторяете N раз во внешнем цикле. Вы повторяете количество раз в зависимости от N во внутреннем цикле.

Также, как вы печатаете треугольник, как

*
**
***
****
*****
******

Количество элементов в треугольнике пропорционально N²

Источник

Время выполнения - это обычно столько шагов, сколько вам нужно сделать.

Асимптотическое время выполнения почти такое же, но вы можете сделать некоторую "магию", чтобы упростить ваш результат.

В вашем случае у вас есть цикл for (int i = 0; i < nums.length; i++) который делает nums.length шаги. И на каждом шагу вы делаете for (int j = 0; j < i; j++),

Ну, сначала вы делаете только 1, затем вы делаете 2 шага, чем 3 шага и т. Д.

Время выполнения 1 + 2 + 3 + 4 + 5 + 6 + .... + nС помощью суммирования рядов вы получите: n*(n+1)/2

Асимптотическое время выполнения основано на некоторых правилах. В нашем случае избавиться от констант можно только n важно, поэтому n*(n+1)/2 = Theta(n*(n)) = Theta(n^2)

Результат: n^2

Источник
Другие вопросы по тегам