Выясните Big O этой минимальной монеты Жадный Algorthm - PullRequest
Новая
       10

Выясните Big O этой минимальной монеты Жадный Algorthm

0 голосов
/ 27 июня 2019 
static void coin(int[] d, int amount) {
        int num_coin;
        for (int i = d.length - 1; i >= 0; i--) {
            num_coin = amount / d[i];
            System.out.println("You should give " + num_coin + " coins of denomination " + d[i]);
            amount = amount % d[i];
        }
    }

В зависимости от того, что я отправлю этому альгортиму, это изменит Большой О? Это значит, что если я отправлю 1 с общей суммой 1, это будет выполнено за O (1) раз, верно? Если я отправлю {1} с общим количеством 5, это будет O (5) или O (n)?

Если бы я отправил {1,4,16,64} в поисках 55, это все равно будет O (n)? n - сумма в массиве

1 Ответ

2 голосов
/ 27 июня 2019

Арифметическая операция (+, -, /, *) имеет O (1)

Вы перебираете массив int d, что создает сложность O (элементы в цикле)

Если предположить, что n - это число элементов в массиве int, то итоговое значение Big O этого алгоритма можно записать в виде O( N + 1 + 1) = O(n)

. Чтобы ответить на ваш вопрос, вы не будете влиять на сложность.этого алгоритма, основанного на значении количества, все, что имеет значение, это количество времени выполнения цикла, которое в этом случае не является фиксированным (т.е. не постоянным)

...