【参考答案】1.6 算法3的空间复杂度是多少？

<p>1. 由于递归而产生的空间复杂度是多少？</p><p><br ></p><p>这个问题是问一共递归了多少层。由于我们每次递归都把搜索范围缩小一半，也就是N/2/2/2...直到得到1，于是有公式N/2^k=1，推出k=log_2 N，即递归最多需要O(logN)次，占用的空间跟递归的次数成正比，也就是O(logN)。</p><p><br ></p><p>2. 算法的整体空间复杂度一共是多少？</p><p><br ></p><p>由于List是作为指针参数传递的，函数内部并没有声明额外的、长度跟N有关的数组，所以每次调用函数都只占用O(1)的额外空间，于是占用的空间跟递归的次数成正比，也是O(logN)。</p><p><br ></p><p>如果考虑整个main函数的空间复杂度，就要把原始List也算在内，它占了O(N)的空间，那么整体空间复杂度就应该是O(N)+O(logN) = O(N)。</p><p><br ></p><p>注意：如果每次传递的不是数组的指针，而是每次复制一段数组，那么递归产生的空间复杂度就变成O(N)了！</p><p><br ></p>