c - 在平均运行时间内使用快速排序时是否可能出现堆栈溢出？

Question

我知道这听起来很愚蠢，但如果我们假设我们很幸运并且每次快速排序的平均时间复杂度为 O(NlogN)，那么无论数组的大小如何，我们都永远不会得到段错误是因为即使我们进行了无数次递归调用并且我们正在为调用堆栈分配空间，但我们从未真正用完整个调用堆栈保留的内存，因为我们在日志时间内将其分解并在线性时间内进行组合。

当然，这是我对我的教授留给我们思考的一个带回家的问题的想法，当我们在类里面出现段错误时。如果我们假设段错误始终具有平均运行时间复杂度，那么我是否认为段错误永远不会发生？

这里是问题:

如果我们有一个堆为 2GB 的计算机系统，并且应用程序的调用堆栈大小为 1MB。并假设每次对快速排序的递归调用都需要将 256 个字节分配给调用堆栈。是否有可能出现堆栈溢出？

编辑:

这是假设我们的算法将以平均时间复杂度运行，并具有问题中注明的计算机规范。抱歉不够具体。

编辑2:

我们的输入大小将等于或小于 2gb，这是我们的堆大小。

Answer 1

如果没有您考虑输入的元素数量，您将无法计算出这一点。在这种情况下，堆栈溢出错误将是“元素数量”和“堆栈大小”的函数。在这些中你错过了一个。