@barakuda1

Как при помощи кучи найти минимальное значение двумерного массива и оценить время работы алгоритма?

Приветствую всех!

Собственно, задача стоит такая: при помощи кучи найти минимальное значение двумерного массива и оценить время работы алгоритма.

const numbers = [[2, 1, 2], [0, 4, 5] ];

var A = Math.min.apply(null,numbers[0]);
var B = Math.min.apply(null,numbers[1]);

if(A < B) {
    console.log(A);
}else
if(A > B) {
    console.log(B);
}else{
    console.log("Найдены одинаковые минимальные значения: " + A + "," + B);
}


Значения выводит корректно, но правильно ли я понял задачу, написав такой код?
Как оценить время работы алгоритма?
  • Вопрос задан
  • 88 просмотров
Пригласить эксперта
Ответы на вопрос 1
Alexandroppolus
@Alexandroppolus
кодир
куча так куча...
function siftDown(arr, i) {
    let chi = i * 2 + 1;
    while (chi < arr.length) {
        const minChildIdx = chi < arr.length - 1 && arr[chi + 1] < arr[chi] ? chi + 1 : chi;
        const chv = arr[minChildIdx];
        if (arr[i] <= chv) break;
        arr[minChildIdx] = arr[i];
        arr[i] = chv;
        i = minChildIdx;
        chi = i * 2 + 1;
    }
}

function heapify(arr) {
    for (let i = Math.floor(arr.length / 2); i >= 0; --i) {
        siftDown(arr, i);
    }
}

function findMinWithHeap(arr) {
    const heap = arr.flat();
    heapify(heap);
    return heap[0];
}

console.log(findMinWithHeap([[2, 1, 2], [0, 4, 5] ]));


время работы O(N), где N - сколько всего элементов в массиве. Надо объяснять почему, или и так понятно?
Ответ написан
Комментировать
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы
29 мар. 2024, в 17:14
4000 руб./за проект
29 мар. 2024, в 17:04
5000 руб./за проект
29 мар. 2024, в 17:03
3000 руб./за проект