Casova zlozitost – C / C++ – Fórum – Programujte.com

potrebujem zistit casovu zlozitost tohto tu: dnes inak to nema cenu

int main()

{

int pole[6] = {0,0,0,0,0,0};

int n; int i; int x;

cin >> n;

for (i=1; i<=n; i++)

{

  cin >> x;

  if (x>6)

    {

           pole[5]+=x/6;

           pole[(x%6)-1]+=1;

           }

    else

      {

           pole[x-1]+=1;

           }       

           }

           

int pp=0;



       if (pole[5]>0){pp+=pole[5]; pole[5]=0;}

       if(pole[4]>pole[0]){pp+=pole[4]; pole[4]=0; pole[0]=0;}

       if(pole[4]<pole[0]){pp+=pole[4]; pole[0]-=pole[4]; pole[4]=0;}

       if(pole[4]==pole[0]){pp+=pole[4]; pole[4]=0; pole[0]=0;}

       if(pole[3]>pole[1]){pp+=pole[3]; pole[3]=0; pole[1]=0;}

       if(pole[3]<pole[1]){pp+=pole[3]; pole[1]-=pole[3]; pole[3]=0;}

       if(pole[3]==pole[1]){pp+=pole[3]; pole[3]=0; pole[1]=0;}

       if(pole[2]%2==0){pp+=(pole[2]/2); }

       else {pole[2]-1; pp+=pole[2]/2; pole[2]=1;}

       

int a=0;

for(i=1; i<=6; i++)

{

       a+=(pole[i-1]*i);

       }

if((a<=6)&&(a!=0)){pp+=1;}

if(a>6){pp+=a/6; if(a%6>0){pp+=1;}}                

cout<<pp;

cin.get(); cin.get();  

return 0 ;

}

1) my (alespon vetsina z nas) nechodi na vejsku jako ty, poroto nevime jak se casova slozitost urcuje ;)

2) jedine co ti mohu poradit je stary program : Borland C 3.1 kde si v options mel takovou vychytavku a videl kde jaka fce zere cas a soucet ;)
bohuzel mi ten program nebere tvuj c++ program - nehledne na to ze tam mas chyby !!!

3) slovicko prosim tu taky nepises

To zacatecnik:1. nechodim na vysku. som v 3 rocniku na strednej.
2. neviem aku chybu mas na mysli mne to bezi bezchyby a plni ucel.
3. vopred DAKUJEM za odpovede

No nejsem si celkem jisty, ale vypada to na linearni casovou slozitost vzhledem k n (asymptoticky, presne se mi to pocitat nechce ;o)).
Mas tam v podstate jeden cyklus od 1 po n, jinak nejaky podminky a pristupy do pole (coz by melo mit konstatni slozitost).

To nickJartin:je tam este jeden cyklus od 1 po 6

To vird: ten cyklus je zanedbatelny pre velke n, teda je to linearne O(n).

To lavor:dik moc velmi ste mi pomohli

To vird: Linearni slozitost se vyznacuje malym mnozstvim zpracovani pro kazdy vstupni element. Nejcasteji to jsou algoritmy, kteere musi zpracovavat N nejake vstupy(resp. N vystupy). Takye se priklanim k navrhu nickJartina.
Pak jeste existuji log N - maji logaritmickou casovou slozitost - vetsinou je poznas, ze resi velke velka zadani a resi problem tak, ze jej v kazdem kroku deli na stejne mensi dily. Meyi tento typ bych napriklad zaradil tzv. binarni vyhledavani. To samoyrejme nejsou vsechny, pak jeste existuji algoritmz s konst. cas. slozitosti, N logN, , kubicku(N^3), kvadratickou(N^2) a exponencialni(2^N, tohle je mimochodem nejmene vhodne).

tobe to slape? tak v cem to kompilujes? i druhy program (visual studio) rve:

--------------------Configuration: cpp - Win32 Debug--------------------

Compiling...

cpp.cpp

C:projektyconsola_backspacecpp.cpp(35) : error C2065: 'cin' : undeclared identifier

C:projektyconsola_backspacecpp.cpp(35) : warning C4552: '>>' : operator has no effect; expected operator with side-effect

C:projektyconsola_backspacecpp.cpp(38) : warning C4552: '>>' : operator has no effect; expected operator with side-effect

C:projektyconsola_backspacecpp.cpp(60) : warning C4552: '-' : operator has no effect; expected operator with side-effect

C:projektyconsola_backspacecpp.cpp(69) : error C2065: 'cout' : undeclared identifier

C:projektyconsola_backspacecpp.cpp(69) : warning C4552: '<<' : operator has no effect; expected operator with side-effect

C:projektyconsola_backspacecpp.cpp(70) : error C2228: left of '.get' must have class/struct/union type

C:projektyconsola_backspacecpp.cpp(70) : error C2228: left of '.get' must have class/struct/union type

Error executing cl.exe.

To zacatecnik:hmm, jasne ze tam chybaj nejaky ten header a namespace, ale to si clovek snad domysli...

samozrejme lavore ! ale on rika ze mu to jede bez toho !?

To zacatecnik:sory asi si nepochopil moj prispevok, ja som myslel ze je zbytocne sa hadat ci to ide alebo nejde bez toho, je jasne ze bez namespace std a nejakeho headru napr. <iostream> to nepojde

Ja by som povedal, ze je to O(n) (ale ruku by som zato do ohna nedal kedze si este celkom niesom isty tym ako by som vypocital ostatne casove narocnosti ...)

to lavor: ne, od programatora se ocekava 100a vice procentni presnost a kdyz rekne, ze ten kod rozjel jak tu stoji a on nejde- neco to o cloveku vypovida !

necetl jsem to tady cele, ale snad casova narocnost se vypocita cas t2(konec)-t1(start), pouzijes nakej timer s vysokou presnosti a je to... dokonce mam na to tridu...

To eMan:to sa mi trochu nezda, casova slozitost sa nemeria na jednotky casu, ale (vacsinou) sa udava ako nejaka funkcia vzhladom k vstupu.
Ide o to ze jeden program moze na roznom systeme bezat rozny cas, ale skusim ti odpovedat tvojim sposobom: vygoogli si to :)

inak je tam na zaciatku este #include <iostream> a using namespace std;
ale cakal som ze si to domyslite sorry
spustam to cez dc++

To lavor: sem jsi to hned myslel že to nebude ono :D

vird píše:#
# inak je tam na zaciatku este #include <iostream> a using namespace std;#
#ale cakal som ze si to domyslite sorry#
#spustam to cez dc++

To zacatecnik: mam taky pocit ze nech poviem cokolvek tak si neico najdes. neviem ci som ti neico urobil ale nevidim dovod preco by si ma mal kritizovat za kazdu blbost.
a to ze od programatora sa ocakava 100percentna presnost....taktiez mozem povedat ze sa ocakava aj nejaky intelekt aby si si vsimol ze tam chyba header ...aje to iba hlavna funkcia.
a ak to ze spustam cez dc++ som povedal lebo tu niekto zahlasil ze pod VS mu to neide. tak preto.
a nepovedal som ze som to rozbehol takto ako to je ale ze mi to bezi ...cely program ... takze neviem fakt

To vird:
mas uplnu pravdu, forum nie je na to aby niekto niekoho kritizoval, zaciatocnik to stale nechce pochopit (aj po tomto prispevku bude mat posledne slovo), ja som ta uplne pochopil a snazil som sa ti pomoct, lebo mam pocit ze to viem (a ak nie tak sa ospravedlnujem za zmatok)

To vird:nie nahodov dev-c++ ?? pretoze dc++ je klient pre P2P siet

To PaLaDiN:no ved chapeme sa :D

samozrejme ze to okomentuju: proste je to nedrozumeni, ja rad chytam lidi za slovicko klidne i ucitele ve skole :) to me naucili na builderu :)
nejde o to ze prudim ze se hadam me to taky nebavi ale jako programtor to musis chapat, celkove mame jinej pristup k zivotu, takze peace :ms_0034:

To zacatecnik: nevim proc zrovna na builderu, tam to funguje celkem v pohode. Takovym tím stylem blba otazka blba odpoved. Jenom tady nemuzes cekat hodne typu lidi jako "Jiri Valerian", kteri nebudou mit zadne keci a proste se za kazdou cenu budou snazit pomahat a klidne stravi psanim prispevku nekolik hodin denne.

nene ja myslim to chytani za slovicka, jako treba i/y to tam miluje obzvlast pan TC. ahoj lidi