Bogosort和O(∞)

Question

众所周知的bogosort算法只是简化了一个套牌,直到它有序

while not inOrder(deck) do
    shuffle(deck);

该算法的复杂度为O(∞).

首先,O(∞)定义明确吗？函数如何在无穷大的常数因子内？

其次,是否有其他众所周知的随机算法具有这种最坏情况的复杂性？(当然没有人会使用bogosort ...)

最后,对于随机算法,在我看来,大多数时候我们只能谈论预期的复杂性.什么时候使用随机算法的大哦？

Answer 1

O(∞)是滥用符号.如果我们对符号严格要求,那么它并不意味着增长受到无穷大因子的限制,因为无穷大不是实数.

如果我们接受这种滥用记谱法的明显含义,即增长"受到无限大的限制",那么很明显它太过于通用而没有多大用处.毕竟什么功能不受无穷大的限制？

因为bogosort的最坏情况运行时间没有真正的上限,所以O(∞)是唯一可以用大哦符号说出来的,正如我们所看到的那样,它并没有真正说明多少.

但是在谈论随机算法时我们仍然可以使用大哦符号:我们只需要分析它有上限的事情.Bogosort有一个最好的情况,最好的情况是在O(n)时间运行.平均而言,它在O(n*n!)时间内运行.