Большая O-нотация - это O (n) или O (n2)? - PullRequest
Новая
       6

Большая O-нотация - это O (n) или O (n2)?

0 голосов
/ 17 февраля 2019

Я написал скрипт, который в основном определяет, сколько ящиков может поместиться в другой (больший) ящик.

У меня есть массив boxes со всеми размерами ящиков и массив products с размерамикоробка каждого продукта. 

let boxes = [
  {label:'box1', width: 4, height: 3, length: 12},
  {label:'box2', width: 6, height: 5, length: 14},
  {label:'box3', width: 8, height: 6, length: 24},
];

let products = [
    {name:'AudioBox3000 ',  width: 2, height:  1, length: 3},
    {name:'Canister1500 ', width: 5, height:  1, length: 11}
];

for(let j = 0; j < products.length; j++)  // O(n)
{
    createDiv('********' + products[j].name + '*********');
  
    for (let i = 0; i < boxes.length; i++)  // O(m)
    {
      let totalWidth  = Math.floor(boxes[i].width  / products[j].width);
      let totalHeight = Math.floor(boxes[i].height / products[j].height);
      let totalLenght = Math.floor(boxes[i].length / products[j].length);
      let totalBoxes  = totalWidth * totalHeight * totalLenght;
      createDiv(totalBoxes + ' boxes fits on ' + boxes[i].label); 
    }
}

function createDiv (value) {
    let div = document.createElement('div');
    div.setAttribute('class', 'app');
    div.innerHTML = value;
    document.body.appendChild(div);
}

Итак, ясно, что for(let j = 0; j < products.length; j++) есть O(n)

и for (let i = 0; i < boxes.length; i++) также O(n)

Так что я 'Я в замешательстве, если это O(n²) или O(n).

Не могли бы вы дать объяснение?

Ответы [ 2 ]

0 голосов
/ 17 февраля 2019

Это ни O(n), ни O(n2).

Давайте рассмотрим N как число продуктов, а M - количество ящиков.

Сложность времени этого алгоритмаравно O(N * M).

Важно различать это 2, потому что, например, давайте представим, что число ящиков является фиксированным числом, например 100 ... Тогда M будет константой и, следовательно, времяСложность алгоритма будет линейной.С другой стороны, если количество ящиков можно выразить как функцию количества товаров, как, например, давайте представим, что количество ящиков - это число товаров степени 2, в этом случае M будет равнодо N ^ 2, поэтому временная сложность будет O(N^3).

Если количество продуктов и количество коробок не связаны вообще, и они оба могут расти по-разному, то временная сложность определенноO(N * M).

0 голосов
/ 17 февраля 2019

Если у вас есть цикл внутри другого цикла, то общая сложность будет O (n * n)

...