硬币算法的复杂性

Question

谁能告诉我这段代码的复杂性(Big O表示法首选)？它找到制作目标总和所需的"硬币"数量最少.为此,它计算从1开始的每个数字的最小硬币数量.每个数字是根据可能与其相加的可能数字对计算出来的,并且使用具有最小成本的数字.一个例子希望这更清楚

如果"硬币"是{1,3,4}并且目标是13则它从1到13迭代,其中2的成本从(0 + 2,1 + 1)开始,c(5)是(c(0)+ c(5),c(1)+ c(4),c(2)+ c(3))等的最小成本,直至c(13)

这是背包问题的一个版本,我想知道如何定义它的复杂性？

码:

import java.util.*;

public class coinSumMinimalistic {
    public static final int TARGET = 12003;
    public static int[] validCoins = {1, 3, 5, 6, 7, 10, 12};

    public static void main(String[] args) {
        Arrays.sort(validCoins);

        sack();
    }

    public static void sack() {
        Map<Integer, Integer> coins = new TreeMap<Integer, Integer>();
        coins.put(0, 0);
        int a = 0;
        for(int i = 1; i <= TARGET; i++) {
            if(a < validCoins.length && i == validCoins[a]) {
                coins.put(i, 1);
                a++;
            } else coins.put(i, -1);
        }
        for(int x = 2; x <= TARGET; x++) {
            if(x % 5000 == 0) System.out.println("AT: " + x);
            ArrayList<Integer> list = new ArrayList<Integer>();
            for(int i = 0; i <= x / 2; i++) {
                int j = x - i;
                list.add(i);
                list.add(j);
            }
            coins.put(x, min(list, coins));
        }
        System.out.println("It takes " + coins.get(TARGET) + " coins to reach the target of " + TARGET);
    }

    public static int min(ArrayList<Integer> combos, Map<Integer, Integer> coins) {
        int min = Integer.MAX_VALUE;
        int total = 0;
        for(int i = 0; i < combos.size() - 1; i += 2) {
            int x = coins.get(combos.get(i));
            int y = coins.get(combos.get(i + 1));
            if(x < 0 || y < 0) continue;
            else {
                total = x + y;
                if(total > 0 && total < min) {
                    min = total;
                }
            }
        }
        int t = (min == Integer.MAX_VALUE || min < 0) ? -1:min;
        return t;
    }
}

编辑:经过研究,我认为复杂性是O(k*n ^ 2),其中n是目标,k是提供的硬币数量,这是正确的吗？

Answer 1

我认为你提供的代码有点混乱.所以这篇文章更多的是关于概念算法而不是真实算法.这可能有点不同,因为例如插入ArrayList<T>不是O(1),但我相信你可以使用好的数据结构(例如LinkedList<T>s)来让所有操作在恒定时间内运行.

您的算法基本上做的是以下内容:

1. 它从一张地图开始,将所有给定的硬币映射到一个:它需要一枚硬币来实现硬币的价值.
2. 对于每次迭代,它将所有已实现的值与所有已实现的值混合.因此,结果是硬币的总和,并且它取硬币数量的总和,除非它已经存在于集合中.
3. 您忘记了这一步:将值严格大于请求的值:由于所有硬币都是严格正数,因此您将永远无法构造一个小于请求值的值.
4. 在构造所请求的硬币值之前,您一直这样做.
5. 如果在迭代时i添加到集合中的所有新值都严格大于请求的值,则可以停止:无法构造所请求的值.

参数是:

• n:硬币数量.
• r:请求的值.

第一个观察是(2.)的每个步骤需要O(s ^ 2)时间,其中s是迭代开始时集合中元素的数量:这是因为您将每个值与每个值匹配.

第二个观察结果是,集合中的元素永远不会超过请求的值.这意味着s以O(r)为界(我们假设所有硬币都是整数,因此该集合最多可以包含从0到r-1的所有整数值).因此,步骤(2)具有O(r ^ 2)的最大时间复杂度.

此外,该集合逐步演变:在每次迭代中,您将始终构造一个至少比最大值大一个值的新值.结果,该算法将执行最大O(r)迭代.

这意味着该算法的时间复杂度为O(r ^ 3):r乘以O(r ^ 2).

为什么行为是指数性的,因此至少NP难？

第一个论点是它表示你如何表示输入:在许多情况下,数字是使用基数大于或等于的系统表示的2.这意味着对于k个字符,您可以表示一个用O(g ^ k)缩放的值,其中g为基数.因此呈指数级.换句话说,如果你使用32比特数,最坏的情况下,r = O(2 ^ 32).因此,如果您将此作为输入,则存在指数部分.如果您使用一元表示法对目标进行编码,则算法在P中.但当然这有点像填充参数:如果你提供了足够无用的输入数据(指数甚至超指数),所有的算法都在P中,但是你不会买太多.

第二个参数是,如果您将所请求的值保留在输入之外,则只能声明您以n个硬币开头.您知道迭代次数是固定的:您将目标值视为未知常量.每次迭代,Map<Integer,Integer>潜在正方形中的值的总数.这意味着计算工作量是:

n+n^2+n^4+n^6+...n^(log r)
^  ^                    ^
|  \-- first iteration  \-- end of algorithm
\-- insertion

很明显,这种行为在n中是指数的.