有哪些见过的时间复杂度为无限大的算法？

在计算机科学领域，我们通常用“时间复杂度”来衡量一个算法在处理输入规模不断增大的过程中，执行时间增长的趋势。对于大多数算法，其时间复杂度是一个有限的、可以用大O符号表示的函数，比如 O(1)、O(log n)、O(n)、O(n log n)、O(n^2) 等等。这些都代表着算法执行时间随着输入规模的增加而以某种可预测、有限的速度增长。

然而，如果我们将目光放宽，从更理论化的角度去思考，或者审视一些在特定场景下行为异常的“算法”或过程，我们确实可以找到一些在某种意义上可以被理解为“时间复杂度无限大”的情况。这里需要强调的是，这更多的是一种概念上的描述，而不是严格意义上一个能被计算的、具有实际执行步骤的算法。

最直观的例子，可以想象一个永不停止的循环。一个程序，如果其逻辑设计使其永远无法到达结束的语句，并且这个循环的执行次数随着某种“输入”或者“状态”的变化而无限增长，那么它的时间复杂度就可以被认为是无限大。

举个例子，设想一个程序，它被设计成不断地查找一个不存在的特定模式。比如说，它在一个由0和1组成的无穷序列中寻找一个连续的“11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111110)

从技术角度来看，这实际上涉及到“不可达”的代码或者程序逻辑的“死锁”。对于这样的“算法”，我们无法为其分配一个有限的时间复杂度，因为它根本就没有结束的可能。

更抽象地说，在数学上，我们可以考虑一些“计算”过程，这些过程即使拥有无限的时间也无法完成。例如，某些证明过程如果依赖于在无穷集合中找到一个满足条件的元素，并且该集合中并不存在这样的元素，那么这个“寻找”过程将永远持续下去，时间复杂度可以被认为等同于不存在。

此外，在计算复杂性理论中，有一个概念叫做“停机问题”，即不存在一个通用的算法能够判断任意给定的程序是否会停止运行。那些不会停止的程序，其“计算”时间就可以被看作是无限的。如果我们把“停机问题”的“非停机”情况当作一种“算法”，那么它的时间复杂度就是无限大。

需要再次强调的是，我们讨论的“时间复杂度无限大”更多是一种理论上对“永不停歇”或“无法终止”计算过程的描述。在实际的算法设计中，我们总是追求有限且高效的解决方案。当一个程序表现出无限运行的迹象时，通常意味着存在逻辑错误、资源耗尽或者需要重新审视算法的终止条件。

在算法的五个性质中就有一个有限性。

1. 输入：一个算法必须有零个或以上输入量。
2. 输出：一个算法应有一个或以上输出量，输出量是算法计算的结果。
3. 明確性：算法的描述必须无歧义，以保证算法的實際执行结果是精確地符合要求或期望，通常要求實際執行結果是确定的。
4. 有限性：依據圖靈的定義，一個演算法是能夠被任何圖靈完備系統模擬的一串運算，而圖靈機只有有限個狀態、有限個輸入符號和有限個轉移函數（指令）。而一些定義更規定演算法必须在有限個步骤内完成任務。
5. 有效性：又称可行性。能够实现，算法中描述的操作都是可以通过已经实现的基本运算执行有限次来实现。

【以上引用自Wikipedia：算法 - 维基百科，自由的百科全书】

换言之，如果有一个时间复杂度为无穷大的程序的话，那它严格地讲就不是算法了。。

从这个角度回答的话，不存在时间复杂度为无穷大的算法。

当然，存在最坏情况会到正无穷但是平均情况下是有穷的算法。

例如说猴子排序。

最坏情况的时间复杂度为O(+∞)，期望时间复杂度为O(n*n!)

不过按照定义来看，猴子排序算不算满足有限性还是个问题。。