时间复杂性Python脚本

Question

我正在编写一个小脚本来猜测数字密码(包括带有前导零的密码).该脚本工作正常但我无法理解该算法的最坏情况时间复杂度.任何关于此实现的复杂性的见解都会很棒,谢谢.

def bruteforce(cipherText):
    for pLen in itertools.count():
        for password in itertools.product("0123456789", repeat=pLen):
            if hashlib.sha256("".join(password)).hexdigest() == cipherText:
                return "".join(password)

Answer 1

首先,在找到正确的密码之前,您总是可能会发现哈希冲突.并且,对于足够长的输入字符串,这是有保证的.所以,实际上,算法是恒定的时间:2^256无论输入是什么,它都将在大约步骤中完成.

但是当你询问它如何以更合理的方式进行扩展时,这不是很有用N,所以让我们假设我们有一些足够低的上限,其中哈希冲突不相关.

现在,如果密码长度为N,则外循环将运行N次.*

_{*我假设这里的密码真的会是纯数字.否则,当然,它将无法找到正确的答案,N并继续前进,直到找到哈希冲突.}

内循环需要多长时间？好吧,它做的主要是迭代每个元素product("0123456789", repeat=pLen).这只是迭代10个元素列表pLen时间的笛卡尔积- 换句话说,产品中有10^pLen元素.

由于10**pLen大于sum(10**i for i in range(pLen))(例如100000 > 11111),我们可以忽略除了最后一次通过外循环的所有内容,因此这10**pLen是内循环的总数.

它在每个内部循环中执行的操作都是线性的pLen(join字符串,散列字符串)或常量(比较两个散列),因此总共有10 ^ pLen*pLen步.

因此,最坏情况的复杂性是指数级的:O(10^N).因为这与乘以N常数然后进行2^cN相同,这与复杂性类相同O(2^N).

如果你想将两者结合在一起,你可以称之为O(2^min(log2(10)*N, 256)).这也是恒定时间(因为渐近线仍然是2^256),但是如果你只关心较小的那么,它表明它是如何实际指数的N.