主页 / 问题 / 838194
Accepted
damintsew
Asked:2020-06-06 02:55:43 +0000 UTC2020-06-06 02:55:43 +0000 UTC

如何计算算法的复杂度？

  • 772

初始数据：具有一列的文件，其中包含从 0 到 Integer.MAX_INT 的数字。

您需要编写一个算法来计算此文件中数字的重复次数。

我们将假设我们有无限量的内存。让我们编写这样一个方法，完成后，只需打印此集合中的条目：

final Map<Integer, Integer> map = new HashMap<>();
//----

public void add(Integer digit) {
    Integer quantity = map.get(digit);

    if (quantity == null) {
        map.put(digit, 1);
    } else {
        map.put(digit, ++quantity);
    }
}

问题 #1：我是否正确理解该方法的算法复杂度为 O(1)？因为 内部使用具有 O(1) 查找的 HashMap 并增加了复杂性。

问题 #2：系统的总复杂度是 O(n) 吗？

现在让我们将其替换HashMap为TreeMap：

问题 #3：该方法的复杂度是 O(log(n)) 吗？

问题 #4：整个系统的复杂度会是 O(n) 吗？因为 它将从 O(n) + O(log(n)) -> O(n) 加起来，因为 它比对数增长得更快。

java

3 个回答

  1. Best Answer

    问题 #1：我是否正确理解该方法的算法复杂度为 O(1)？因为 内部使用具有 O(1) 查找的 HashMap 并增加了复杂性。

    是的，附带条件是对坏数据的哈希插入/查找可以降级到O(n)，

    这里值得一提的是，对于具有足够哈希函数、合适的表大小和准随机输入数据的哈希，最坏情况的概率可以忽略不计，但这种情况总会给出一组数据。通常它可以被专门拾取，甚至用于DOS 攻击。

    另外，在动态扩展哈希表的通常实现中map.put，可能需要重建哈希索引，其复杂度也是O(n)，但可以通过提前为表分配足够的数据量来避免这种情况.

    问题 #2：系统的总复杂度是 O(n) 吗？

    是的，有一个类似的警告，在最坏的情况下，时间将是O(n²)。

    在典型实现中动态扩展哈希表的情况下，还需要增加其大小并重新计算时间顺序的哈希，log(N)时间会相应恶化到平均O(N*log(N))情况下，但这种效果只会出现在相对较大的情况下，N并且通常以一种或另一种方式出现，它可以被拉平（分配明显更多的内存）。

    现在让我们用 TreeMap 替换 HashMap：

    问题 #3：该方法的复杂度是O(log(n))吗？

    是的

    问题 #4：整个系统的复杂度会是 O(n) 吗？因为 它将从 O(n) + O(log(n)) -> O(n) 加起来，因为 它比对数增长得更快。

    不，这不是真的：您需要N以复杂度O(log(n))执行一次操作，其中n平均值为N/2。那些。复杂度将为O(N*log(N))。

    • 8

  2. 是的，一切都是正确的。遍历一个集合总是 O(N)，因此执行 add 方法并打印所有元素是 O(N)。在第一种情况下，add函数的复杂度平均为O(1)（最坏的情况下为O(N)，因为哈希表中可能存在冲突），在第二种情况下，为O( log N) 在最坏的情况下，因为 TreeMap 是平衡二叉搜索树。

    UPD不幸的是，我有点看错了，我忘记了在第二种情况下我们为对数添加了N次，因为复杂度是O（N log N）

    • 5

  3. “我们需要编写一个算法来计算这个文件中 数字的重复次数 。”

    HashMap告诉我，如果您对数字感兴趣，为什么需要任何数字？一个 10 个整数的数组，并且向前，一次读取一个字符，如果是一个数字 - 增加数组的相应元素。全部。清洁O(размер файла)。

    作业写对了吗？只是在你有一个任务的情况下，你解决了一个完全不同的任务。

    • 1

相关问题