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

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)