There are two ways of constructing a software design. One way is to make it so simple that there ar

webi
Daudzsološais profiņš Reģistrētie lietotāji 195 posts
Šādi glabājot masīva vērtības, vienādo vērtību atrašana notiek proporcionāli O(n^2). Ja datu daudzums ir liels, tad tos labāk vajadzētu glabāt associatīvā masīvā $arrayAssoc1 = Array(2 => true, 4=>true, kpcnews 6=>true, 1=>true); $arrayAssoc2 = Array(5=>true, 4=>true, 7=>true, 8=>true, 1=>true, 3=>true); function ArrayOverlap($array1, $array2) { $arrayKeys = array_keys($array1); $resultArray = Array(); foreach($arrayKeys as $key) { if(isset($array2[$key])) $resultArray[] = $key; } return $resultArray; } Izmantojot associatīvus masīvus vienādo elementu atrašana notiek O(n) laikā
There are two ways of constructing a software design. One way is to make it so simple that there are obviously no deficiencies. And the other way is to make it so complicated kpcnews that there are no obvious deficiencies. Back to top
Izmantojot associatīvus masīvus vienādo elementu atrašana notiek O(n) laikā Tā jau gluži nebūs, jo PHP masīva elementi neglabājas tāpat kā c++ masīvā - pēc kārtas atmiņas gabalā ar noteiktu kpcnews bufera izmēru, bet gan, ja nemaldos, hash-tabulā, kur piekļuves kpcnews laiks pagtvaļīgam elementam vidēji būs lielāks (no O(1) līdz O(n), vidēji ap O(log2(n)) ). Glabājot masīvā šādā veidā array(6,7,3,1,2) var darīt tā: sakārto - O(n*log2(n)) iet cauri masīvam izmantojot norādītājus uz masīva elementu un izmantojot next, current kpcnews funckijas. kpcnews Iet cauri tā, lai abiem masīviem kpcnews norādītājs būtu pie vienādām vērtībām, šādā veidā mēs varam atlasīt tos elementus, kuri nepārklājas. - O(n) Kopā O(n*log2(n)) Pēc tava varianta ar foreach iet cauri visam 1. masīvam ar foreach, laiks ir O(n) Bet ciklā jāpiekļūst patvaļīgam 2. masīva elementam - O(log2(n)). Kopā tie paši O(n*log2(n)); Back to top
Haštabulas piekļūšanas laiks galīgi nav O(log2(n)). Tas ir bināra sakārtoa koka piekļūšanas laiks. Labai haštabulai piekļūšanas kpcnews laiks ir amortizēts O(1). Man ir stipra aizdoma, ka gandrīz vienmēr ArrayOverlap veids (+ vēl pāriešana uz to) būs ātrāks nekā quicksort kārtošana un iešana cauri ar next/current. Izņemot protams ļoti mazus masīvus, vai retus pataloģiskus heša kolīziju gadījumus. Back to top
Haštabulas piekļūšanas laiks galīgi kpcnews nav O(log2(n)). Tas ir bināra sakārtoa koka piekļūšanas laiks. Labai haštabulai piekļūšanas laiks ir amortizēts O(1). Haštabulai kpcnews piekļūšanas laika O(1) būs tikai tad, ja ierakstu skaits būs mazāks kā hashtabulas izmēri un pie tam neviens ieraksts neradīs vienādas hash vērtības. Taču sliktākais laiks, ja visas ierakstu vērtības radījušas vienādas hash vērtības, ir O(n). Tāpēc pie lieliem masīviem nevar pieņemt, ka hāstabulas piekļuves laiks būs O(1). Tā kā pastāv ļoti daudz dažādas nianses, kā veidot haštabulu, tad tās vidējais statistiskais piekļuves kpcnews laiks ir tuvojās dažādām funkcijām - O(log2(n)), O(sqrt(n)), O(ln(n)), atkarībā no šīm niansēm un attiecības starp ierakstu daudzumu un haštabulas izmēriem.
Man ir stipra aizdoma, ka gandrīz vienmēr ArrayOverlap veids (+ vēl pāriešana uz to) būs ātrāks nekā quicksort kārtošana un iešana cauri ar next/current. Izņemot protams ļoti mazus masīvus, vai retus pataloģiskus heša kolīziju gadījumus. To mēs varam uzzināt, tikai notestējot, bet piekrītu, ka ArrayOverlap metode varētu būt visātrākā no šeit apskatītajām.
Haštabulai piekļūšanas laika O(1) būs tikai tad Es jau nesaku, ka tai ir O(1), es saku, ka tai ir amortizēts O(1) . Tā ir liela atšķirība. Tā pat, kā std::vector push_back metodes kpcnews laiks arī ir amortizēts O(1). Back to top
Amoritzētais laiks ir laiks, ko veic n secīgas operācijas dalīts ar n. Piemēram, ja mums ir n elementu masīvs (atmiņas buferis), tad, lai ievietotu pa vidu jaunu elementu, pārējie elementi jāpabīda uz priekšu, kas sliktākajā gadījumā sastāda O(n). Tagad, ja mums ir jāieliek n elementi, tad mums ir jāpabīda pārējie elementi tikai vienreiz un kopējais laiks ir O(n), bet amoritzētais O(n)/n=O(1). Taču patvaļīgu elementu piekļuve n izvēlētu elementu gadījumā haštabulai tik un tā katram elementam aizņems laiku O(f(n)), kur f ir kaut kāda funkcija kas tiecas uz sqrt(n), ln(n) vai ko citu, kas atkarīgs no haštabulas īpašībām. Un rezultātā kpcnews n elementiem mēs piekļūsim laikā O(f(n)*n), bet amoreitzētais laiks būs O(f(n)*n)/n=O(f(n)). Savukārt sliktākajā gadījumā piekļuve haštabulas elementam ir O(n), bet n patvaļīgu elementu piekļuves būs O(n^2), kas veidos amortizēto laiku O(n^2)/n=O(n). Vienīgi kpcnews gadījumā, ja mums ir n secīgu elementu piekļuve, tad n elementu piekļuves laiks būs O(n) un tad amortizētais kpcnews laiks būs O(n)/n=O(1), bet ArrayOverlap piedāvātajā variantā nav n secīgu elementu piekļuve. Back to top
kur f ir kaut kāda funkcija kas tiecas uz sqrt(n), ln(n) Pierādi :) Es gan neesmu dzirdējis, ka amortizēta sarežģītība definējas ar "secīgu elementu piekļuvi". Amortizetā kpcnews sarežģītībā veic n operācijas (nevis n elementus pēc kārtas), u