Digamos que eu defina uma função da seguinte forma, que aceite um argumento a
que seja um array bidimensional de números:
function totalSum(a) {
let total = 0;
for (const elem of a) {
for (const subElem of elem) {
total += subElem;
}
}
return total;
}
// Exemplo de entrada:
totalSum([[1, 2], [3, 4]]); // 10
Ela pode ser classificada como tendo complexidade O(n²), certo?
Agora no contexto de outra função, que aceita dois argumentos, a
e b
, ambos arrays unidimensionais:
function allIncludes(a, b) {
let allExists = null;
for (const aElem of a) {
// Note que o `includes` abaixo irá iterar sobre cada elemento de `b` até o
// fim dos elementos, ou até que algum elemento seja igual a `aElem`.
// Uma complexidade próxima de `O(n)`.
if (includes(b, aElem)) {
// Se `exists` já for `true`, irá continuar como `true`.
// Se for `false`, não será atribuído.
if (allExists === null) {
allExists = true;
}
} else {
allExists = false;
}
}
return allExists;
}
// Ignore:
function includes(arr, elem) {
for (const el of arr) {
if (el === elem) {
return true;
}
}
return false;
}
// Exemplo de entrada:
allIncludes([1, 2, 3], [3, 2, 1]); // true
allIncludes([1, 2, 3], [1, 2, 4]); // false
Essa última função pode ser classificada com complexidade O(n²)? Pergunto isso porque, diferentemente da primeira função desta pergunta, allIncludes()
irá aceitar dois argumentos, que podem ser de tamanhos diferentes.
Eu pessoalmente considero esse um caso de "quase O(n²)" ou "um pouco mais que O(n²)", mas com certeza essa denominação informal da minha parte não está correta.