algorithm - 与输入数量及其大小有关的时间复杂度
问题描述
我有一个算法，我有多个任务，对于每个任务，我必须执行与任务长度（以分钟为单位）一样多的操作。行动成本为O(1)。这是伪多项式、多项式还是指数算法？
这很容易让人想起素数朴素算法或背包动态规划解决方案，但这种情况略有不同。考虑有 3 个任务，它们的长度是5; 4; 10;，用二进制表示：101; 100; 1010;。我们必须执行 19 个动作。现在，如果我们通过在前面添加一位来将第一个任务长度从 更改为 ，现在我们必须执行 27 个101动作。1101动作的数量不会像在朴素素数解决方案中将一位添加到一个数字的情况下加倍，而是乘以27/19. 如果有更多的任务，变化会更小。换句话说，算法复杂度与输入的长度和任务的数量有关。