Path algoritm complexity ile alakali bi soru

[Larva]

Simdi odevimde logic devresini baya garip bi notasyonda okuyup insanlar icin anlasilir hale getiren bi kod yaziyorum, herseyi bitti yalnizca her nodelari levelize eden kismin complexity sinden emin olamadim. Onu soruyorum ve de daha iyi bir yontem var mi diye merak ediyorum.

Kisaca yapilcak islem surda elimizde de su sekilde bagli bir linked list structure i var.

structure

	typedef struct n_struc {

	   unsigned indx;             /* node index(from 0 to NumOfLine - 1 */

	   unsigned num;              /* line number(May be different from indx */

	   enum e_gtype type;         /* gate type */

	   unsigned fin;              /* number of fanins */

	   unsigned fout;             /* number of fanouts */

	   struct n_struc **unodes;   /* pointer to array of up nodes */

	   struct n_struc **dnodes;   /* pointer to array of down nodes */

	   int level;                 /* level of the gate output */

	   int NumInpsReady;

	} NSTRUC;                     

	

	

.


Bu da benim bu is icin yazdigim kod.

	inputLevelize()

	{

		int i,j;

		

		for(i = 0; i<Npi; i++) {

			Pinput[i]->level=0;

			for(j = 0; j<Pinput[i]->fout; j++) 

				Pinput[i]->dnodes[j]->NumInpsReady++;

				Pinput[i]->NumInpsReady++;

		}

		Nlev=Npi;

		for(i = 0; i<Npi; i++) 

			findAndLevelize(Pinput[i]);

	

	}

	findAndLevelize(NSTRUC *nd){

		NSTRUC *np;	

		int i,j;

	

		for(i = 0; i<nd->fout; i++)

		{		

			np = nd->dnodes[i];

			if(np->NumInpsReady == np->fin)    //node level icin uygunsa

			{ 

				np->level=findMaxInputLevel(np)+1;

				for(j = 0; j<np->fout; j++) np->dnodes[j]->NumInpsReady++;

				np->NumInpsReady++;

				Nlev++;

				findAndLevelize(np);    // o node dan devam et

			}

		}

	}

	

	findMaxInputLevel(NSTRUC *np)

	{

	int i,max=0;

		for(i = 0; i<np->fin; i++)

			if(max < np->unodes[i]->level)

			max=np->unodes[i]->level;

		return max;

	}

	

Iterative olarak da yaptim once ama onun best case n worst case de n^2 oldugunu biliyorum acaba recursive olunca direk linear mi oldu?

[Larva]

Alakali soruyu da tam olarak yaziyim farkli fikri olan varsa belirtebilir

soru

What I the complexity of your procedure in terms of the number of lines in the
circuit and any other parameter that you think affects the complexity
significantly?

[syd]

sen hwinkini mi soruyorsun swinkini mi?