时间戳

首页 > 解决方案 > 找出这个最小硬币贪婪算法的大 O

algorithm - 找出这个最小硬币贪婪算法的大 O

问题描述

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];
        }
    }

取决于我发送这个算法的内容，这会改变它的大 O 吗？意思是，如果我发送一个总量为 1 的 1，它将运行 O(1) 时间，对吧？如果我发送总共 5 个的 {1}，那是 O(5) 还是 O(n)？

如果我发送 {1,4,16,64} 寻找总共 55 个，那仍然是 O(n) 吗？n 是数组中的总数

标签： algorithmbig-o

解决方案

算术运算 (+, -, /, *) 有一个 O(1)

您正在循环 int 数组d，这会产生 O(items in loop) 的复杂性

假设 n 是 int 数组 d 中的项目数，那么这个算法的最终 Big O 可以写成，O( N + 1 + 1) = O(n)

为了解决您的问题，您不会根据数量的值影响该算法的复杂性，重要的是循环运行的次数，在这种情况下它不是固定的（即不是恒定的）

推荐阅读