big O - qual seria a prossível notação desse código? [RESOLVIDO]

1. big O - qual seria a prossível notação desse código? [RESOLVIDO]

Samuel Leonardo
SamL

(usa XUbuntu)

Enviado em 02/06/2022 - 03:23h

Olá, eu tenho essa função recursiva abaixo e gostaria de saber a notação de complexidade dela:
bool combina(float porcAtual, float porcAlvo, int maxCombs, int currentStack, int tryingSorts, int saiuMin, int alvo, std::vector<int> ids, std::vector<int> & idsCombs, std::vector<std::vector<int>> & sorteios, std::vector<std::vector<int>> &combsBase, std::vector<std::vector<int>> &out) {
if (currentStack > maxCombs)
return 2;

std::vector<int> logic;
for (int i =0; i < 100; i++)
logic.push_back(i);

for (int i = 0; i < tryingSorts; i++) {
int p = combsBase.size() * RandNum();
if (combsBase.size() && !hasNum(idsCombs, p)) {
idsCombs.push_back(p);
auto &v = combsBase[p];
float currentPorc = 0;
int c = 0;
if (ids.size() == 0 && currentStack == 0) {
for (int j = 0; j < alvo - 1; j++) {
if ((saiuMin >= 0 && countSort(v, sorteios[j]) >= saiuMin) || (saiuMin < 0 && countSort(v, sorteios[j]) <= abs(saiuMin))) {
c++;
ids.push_back(j);
}
}
currentPorc += c / float(alvo - 1);
}
else if (ids.size()) {
if (ids.size() == 1) {
return 0;
}
for (auto &j: ids) {
if ((saiuMin >= 0 && countSort(v, sorteios[j]) >= saiuMin) || (saiuMin < 0 && countSort(v, sorteios[j]) <= abs(saiuMin))) {
c++;
}
}
currentPorc = (float(c) / float(ids.size()));
}

if (combina(porcAtual + (porcAlvo == 0)? 0: currentPorc, porcAlvo, maxCombs, currentStack + 1, tryingSorts, saiuMin, alvo, ids, idsCombs, sorteios, combsBase, out) == 1) {
if (currentStack > 0)
out.push_back(v);
return 1;
}
}
}
return 0;
}

Por favor, descosidere eventuais erros de sintaxe ou compilação.

Em qual categoria do big O, aproximadamente, se encaixa essa minha função?


  


2. MELHOR RESPOSTA

Paulo
paulo1205

(usa Ubuntu)

Enviado em 04/06/2022 - 14:07h

Não sou especialista em análise de complexidade, mas fiz alguns comentários ao longo do código (além de alguma alterações em sua forma) que acredito que podem ser úteis.
bool combina(
float porcAtual, float porcAlvo,
int maxCombs, int currentStack,
int tryingSorts, int saiuMin, int alvo,
std::vector<int> ids, // Passagem por valor, que para std::vector é O(n).
std::vector<int> &idsCombs, // Não poderia ser const?
std::vector<std::vector<int>> &sorteios, // Não poderia ser const?
std::vector<std::vector<int>> &combsBase, // Não poderia ser const?
std::vector<std::vector<int>> &out
){
// A variável saiuMin é constante ao longo da função, então seu valor
// absoluto não precisa de ser calculado dentro de um laço de repetição.
unsigned abs_saiuMin=abs(saiuMin);

/*
A condição de parada da recursividade parecer estar aqui: você efetiva-
mente conta quantas vezes a função foi chamada com os mesmos dados, e
interrompe a chamada recursiva caso uma certa quantidade de chamadas
tenha sido ultrapassada.

Se o parâmetro maxCombs não depender do número de elementos dos parâ-
metros que são vetores ou matrizes, a recursividade pode ser conside-
rada O(1). Se depender — numa relação que tenha ocorrido fora da fun-
ção, antes da primeira chamada — pode levar a recursividade a O(n),
caso se considerem os elementos do vetor, ou mesmo O(n^2), caso dependa
das dimensões das matrizes.

Note, porém, que as considerações acima aplicam-se apenas às chamadas
recursivas, não à complexidade do algoritmo por ela implementado. Como
se verá abaixo, os laços de repetição e as chamadas internas que acon-
tecem cada vez que a função é chamada têm suas próprias contribuições
à complexidade total.
*/
if (currentStack > maxCombs)
return 2; // XXX: Lembre-se que o tipo de retorno é bool; 2 é int.
// Você quis dizer “return true;”, ou teria de trocar
// o tipo de retorno?

// XXX: Para que criar e inicializar um array com 100 elementos que não
// será usado no restante da função?
std::vector<int> logic;
for (int i =0; i < 100; i++)
logic.push_back(i);

// Varredura linear de [0..tryingSorts[: pode indicar O(n).
for (int i = 0; i < tryingSorts; i++) {
int p = combsBase.size() * RandNum(); // XXX: RandNum() retorna valor
// dentro de [0.0; 1.0[,
// certo? Se não, é bug.

// hasNum() opera com um vetor: grandes chances de ser O(n).
// Combinando com o laço de repetição, já podemos ter O(n^2).
if (combsBase.size() && !hasNum(idsCombs, p)) {
idsCombs.push_back(p);
auto &v = combsBase[p]; // v é um vetor.
float currentPorc = 0; // XXX: Escolha de nome: mistura Inglês, e
// ainda usa conceitos semelhantes
// (“atual” × “corrente”).
int c = 0;
if (ids.size() == 0 && currentStack == 0) {
// XXX: Rearrumei laço de repetição contendo if com condição
// e chamada de função invariantes, deixando como um
// if/else externo contendo laços de repetição mais simples
// contendo chamada de função.

int lim=alvo-1;

// Em qualquer dos dois casos abaixo, countSort() opera em cima
// de dois vetores independentes. É de se esperar que isso faça
// dela ou O(n) ou O(n^2). Isso pode levar o total para O(n^3)
// ou O(n^4) esperados.
if(saiuMin>=0){
for(int j=0; j<lim; ++j)
if(countSort(v, sorteios[j])>=saiuMin){
++c;
ids.push_back(j);
}
}
else{
for(int j=0; j<lim; ++j)
if(countSort(v, sorteios[j])<=abs_saiuMin){
++c;
ids.push_back(j);
}
}
currentPorc += c / float(lim);
}
else if (ids.size()) {
if (ids.size() == 1)
return 0; // XXX: int em função declarada como bool.

// XXX: Também aqui uma rearrumação considerando invariantes.

// Em qualquer dos dois casos abaixo, countSort() opera em cima
// de dois vetores independentes. É de se esperar que isso faça
// dela ou O(n) ou O(n^2). Isso pode levar o total para O(n^3)
// ou O(n^4) esperados.
if(saiuMin>=0){
for(int j: ids)
if(countSort(v, sorteios[j])>=saiuMin)
++c;
}
else{
for(int j: ids)
if(countSort(v, sorteios[j])<=abs_saiuMin)
++c;
}

currentPorc = (float(c) / float(ids.size()));
}

if (
combina(
(porcAlvo==0.f? porcAtual: porcAtual+currentPorc), porcAlvo,
maxCombs, currentStack + 1,
tryingSorts, saiuMin, alvo,
ids, // Cópia de elementos de ids (O(n)).
idsCombs,
sorteios,
combsBase,
out
) == 1 // XXX: valor int em função declarada como bool.
) {
if (currentStack > 0)
out.push_back(v);
return 1; // XXX: valor int em função declarada como bool.
}
}
}
return 0; // XXX: valor int em função declarada como bool.
}



... Então Jesus afirmou de novo: “(...) eu vim para que tenham vida, e a tenham plenamente.” (João 10:7-10)

3. Re: big O - qual seria a prossível notação desse código? [RESOLVIDO]

Samuel Leonardo
SamL

(usa XUbuntu)

Enviado em 06/06/2022 - 09:54h

Opa, desculpe a demora pra responder.
Daqui a pouco vou ler com mais calma tuas considerações, Paulo.
De qualquer forma, fica meu obrigado.


4. Re: big O - qual seria a prossível notação desse código? [RESOLVIDO]

Samuel Leonardo
SamL

(usa XUbuntu)

Enviado em 07/06/2022 - 05:07h

Obrigado pelas observações, Paulo, você disse coisas que eu tinha apenas leve noção.
Quanto ao código desarrumado é porque faz parte de um programa pessoal, daí o relaxamento com eventuais erros bobos como trocar bool por int.
Vou fechar o tópico.
Valeu.






Patrocínio

Site hospedado pelo provedor RedeHost.
Linux banner
Linux banner

Destaques

Artigos

Dicas

Tópicos

Top 10 do mês

Scripts