二分木を用いた数値配列の部分範囲内の最大値取得 - Qiita

function findMax(nums, start, end, minValue = -Infinity) { let maxValue = minValue; for (let i = start; i < end; i++) { maxValue = Math.max(maxValue, nums[i]); } return maxValue; } ただしこの方法では、一度の検索が線形時間であるため、数万要素数ある配列の場合、何度も範囲を変えながら最大値を求めるような場合には、とても大きな時間がかかってしまいます(繰り返したときの計算量はO(N^2))。 二分木による実装 そこで、これを回避するには、最大値を収めた二分木を一度作成することによって、対数時間で検索できるようになります(繰り返したときの計算量はO(NlogN))。 function createMaxTree(num