我今天参加了一次实习面试,但是我无法解决这个问题。
total = 0
product(int array[]) {
if (array.length == 1) {
return array[0]
} else {
product(product right side array * product left side )
}
}
我今天参加了一次实习面试,但是我无法解决这个问题。
total = 0
product(int array[]) {
if (array.length == 1) {
return array[0]
} else {
product(product right side array * product left side )
}
}
product(左侧)* product(右侧)
将返回一个唯一的数字,因此对product
的外部调用将采用O(1)。
这两个内部调用仅仅是在数组中执行二叉树深度优先遍历,这需要O(n)时间。
然而,在每个遍历的层级中,它都在执行对product
的外部调用,且有O(logn)个级别,每个级别的成本为O(1),因此该成本乘以O(logn),您就会得到O(nlogn)。
product right side array
和product left side
都涉及n/2个元素(将数组分为2部分),因此操作数为product(product right side array * product left side )
的“深度”是 log n(如果从 256 开始,则递归调用的“深度”将为 8),因为每次数组的大小都是初始大小的一半。由于最终返回了 n 个元素,因此时间复杂度为 O(n log(n))。递归树的高度最多为log_2 n,因为这是在到达n = 1(即叶节点)之前可以将n折半的次数 - 将log_2 n视为n中位数的数量。
树的每个级别的宽度最多为n(在底部,每个数组元素仅访问一次;树的上层显然更窄)。
在每个分支处,执行一个常量时间(O(1))乘法操作(假设对于此参数,数组拆分是恒定时间)。
因此,操作次数的上限为O(1) x n x log_2 n = O(n log n)。
product(left side) * product(right side)
?我删掉了我的回答,它是错误的。 - JosEduSol