Какова временная сложность деления массива на n подмассивов? - PullRequest
Новая
       27

Какова временная сложность деления массива на n подмассивов?

1 голос
/ 12 марта 2020

Я написал следующую программу, которая разбивает массив на подмассивы размера, используя функцию среза JS, я пытаюсь выяснить временную сложность этого алгоритма: 

function chunk(array, size) {
    if(array.length < size)
        return [array];

    let result = [];

    for(let i = 0; i < array.length; i += size)
            result.push(array.slice(i, i+size));

    return result;
}

My текущее понимание состоит в том, что сложность составляет O (n * size), потому что мы перебираем времена размера всего массива. Если бы кто-то мог помочь мне понять это решение, оно было бы очень признательно! Спасибо!

1 Ответ

3 голосов
/ 12 марта 2020

Это O(n).

. Итерация по массиву n/size раз, и каждая итерация O(size), потому что она создает срез size элементов. Таким образом, общий объем работы составляет n/size * size, что составляет n.

...