我已经了解如何计算算法的时间和空间复杂度，并且我发现了一个有趣的训练问题。
// count the occurrence of an element in an array
// list is already sorted
function count (list, item, start, end) {
if (start > end) {
return 0;
}
const mid = Math.floor((start + end) / 2);
if (list[mid] < item) {
return count(list, item, mid + 1, end);
}
if (list[mid] > item) {
return count(list, item, start, mid - 1);
}
return count(list, item, start, mid - 1) + 1 + count(list, item, mid + 1, end);
}
答案是O(n)。我认为它应该是对数的东西。有人可以向我解释，为什么我错了？
考虑列表的所有元素都等于 的情况item。在这种情况下，您将只使用 first 和 last return。因此，您可以n = end - start大致编写算法的运行时：
T(n) = O(1) + 2 * T(n/2)
这解决了T(n) = O(n).
本文收集自互联网，转载请注明来源。
如有侵权，请联系 [email protected] 删除。
我来说两句