在java中-假设有一个while循环运行logn次，那么时间复杂度为o（logn），在该循环中，我在每次迭代中声明一个大小为2的数组：
While (high > low)
Int[] arr = arrFunc(mid, 0);因此，在每次迭代中，我们都创建一个在前一个数组上运行的数组，因为它被java垃圾收集器“销毁”。那么空间复杂度o（1）呢？还是o（logn）？
在java中-假设有一个while循环运行logn次，那么时间复杂度为o（logn），在该循环中，我在每次迭代中声明一个大小为2的数组：
While (high > low)
Int[] arr = arrFunc(mid, 0);因此，在每次迭代中，我们都创建一个在前一个数组上运行的数组，因为它被java垃圾收集器“销毁”。那么空间复杂度o（1）呢？还是o（logn）？
1条答案
按热度按时间polkgigr1#
空间复杂性的概念是语言不可知的。
在这里，由于您在每个迭代中创建一个新的结构，所以您增加了同样多的空间复杂性。
如果你的算法是
O(log n)在时间复杂度上，这部分的空间复杂度也是O(log n)还有，别忘了O是算法可能达到的上限。它不是算法将使用的实际空间。正如@luk2302正确指出的，如果您的算法不是每次都创建一个新数组，而是使重用现有数组成为可能，那么您的空间复杂度将下降到
O(1)