密码散列函数的时间复杂度是多少？
比方说MD5或SHA-1？这两者的时间复杂度是多少？我试图在网上找到它，但它非常有限，我得到的只是它们都是O（n）。有人能进一步启发我吗？也许给我一个最坏的情况和最好的情况？
共有1个答案
MD5和SHA-1算法都是基于Merkle Damgard构造的，这两种算法都不安全，不应该再使用了。这意味着它们是由
- 从分组密码开始，该分组密码将固定宽度的位块作为输入，并输出相同大小的固定宽度位块，
- 使用加密安全的填充方案将输入填充到块大小的几倍，然后
- 以迭代方式将分组密码应用于输入的若干位以及初始化值或前一个分组密码的输出的组合。
因为分组密码工作在固定大小的比特块上，所以运行它的时间复杂度是O（1）。该分组密码总共有θ（n）个应用程序（输入被拆分为固定大小的块，因此这些块有θ（n）个），计算填充位的成本可能是O（1），但可能是O（n）。总的来说，这意味着计算这些散列函数的运行时间是θ（n），这是有意义的，因为每个位至少被访问一次，并且每个位所做的工作是恒定的。
分组密码的实现方式通常使它们在任何输入位组合上运行完全相同的时间 - 或者至少非常接近相同的时间量 - 以试图使它们抵抗定时攻击，其中计算分组密码所需的时间量用于窃取某些位。因此，如果这些哈希函数在相同大小的不同输入上花费不同的时间来完成，那将是非常不寻常的。因此，与运行时为 Θ（n） 这一事实无关，您不应该期望看到挂钟运行时有太大变化。
-
好的，第一个for循环显然是。第一个迭代是，第二个迭代是。我想是不是就像那个次数？这意味着。我说对了吗？ 编辑：（不是复制品）我知道大O是什么。我在一个具体的案例中询问了正确的评估。
-
我对这个话题很陌生，我正试图掌握与渐近符号相关的一切。我想就以下问题征求你的意见: 如果我们有，对于一个算法，T（n）=n！，那么我们可以说它的时间复杂度： 这个关系意味着n！=O（n^n）和n！=ω（1）。然而，我们不能做得更好吗？我们希望big-oh尽可能接近函数T（n）。如果我们做以下操作： 也就是说，对于倒数第二个元素，我们将 （n-1） 替换为 n。现在这种关系不是真的吗？那么n不是真的
-
问题内容： 我正在写一个看起来像这样的python函数 因此它被称为 我以为列表的索引访问权限为，但是很惊讶地发现对于大型列表，这比我预期的要慢得多。 那么，我的问题是如何实现python列表，以及以下代码的运行时复杂度是多少？ 索引： 从结尾弹出： 从一开始就弹出： 扩展列表： 对于额外的信用，剪接或任意弹出。 问题答案： 在python Wiki上 有一个非常详细的表格，可以回答您的问题。 但
-
问题内容： 我当时在看这个pycon演讲，时间是34:30，发言人说，可以在中完成获取元素列表中最大的元素的操作。 那怎么可能？我的理解是，创建堆将是，但是其本身的复杂性是还是（以及（实际的算法是什么））？ 问题答案： 扬声器在这种情况下是错误的。实际费用为。仅在可迭代的第一个元素上调用堆化。就是那个，但如果小于，则微不足道。然后，将所有剩余的元素一次通过添加到此“小堆”中。每次调用需要花费时间。
-
Leetcode问题https://leetcode.com/problems/count-binary-substrings/ 该解决方案有效，但我很难提出递归解决方案的时间复杂度。 每当循环遇到s.charAt（i）！=s.charAt（i 1）时，它都会进行递归调用以展开，直到达到基本大小写或其他部分。 因为我遍历整个字符串，所以for循环是O（n）。但是如何确定将进行的递归调用的数量，因为
-
我写了一个函数来寻找目标值在给定数组中应该插入的位置。我们假设数组有不同的值，并按升序排序。我的解必须是O(log N)时间复杂度 此代码的复杂性是否为O（log N）？