Ad argvmentvm transi
Topos Uranos
Latine

Svmptvs algorithmi

Svmmarivm

Adhvc cvrsvs algorithmos vna tantvm qvaestione ivdicavit: facivntne qvod dicvnt? Haec lectio alteram addit, qvae decernit an programma rectvm in vsv valeat: qvanti constat? Svmptvs primvm sine horologio metimvr, nvmerando qvoties operatio dominans exseqvatvr, et fvnctio magnitvdinis nn datorvm esse invenitvr. Qvod in ea fvnctione interest non est valor eivs pro dato nn, sed qvomodo crescat: tabvla ipsorvm nn, nlog⁡nn \log n, n2n^2 et 2n2^n ostendit discrimina inter algorithmos, cvm decem datis invisibilia, cvm decies centenis milibvs abyssos fieri. Notatio OO vt abbreviatio horvm ordinvm incrementi proponitvr, sine definitione formali, cvm exemplis iam in cvrsv visis: Evclides, logarithmicvs; svmma vectoris, linearis; omnivm parivm comparatio, qvadratica; Fibonacci simplex, exponentialis. Deinde horologio ipsivs <chrono>, std::chrono::steady_clock, metimvr, et discitvr cvr vna mensvra fallat, cvr cvm optimizatione et sine detectoribvs metiamvr, et qvomodo mensvra cvm praedictione conferatvr: dvplicato nn, algorithmvs linearis tempvs svvm dvplicat et qvadraticvs qvadrvplicat.

Proposita discendi

  1. Operationes dominantes algorithmi vnvm dvosve circvitvs habentis nvmerare secvndvm magnitvdinem nn datorvm.
  2. Algorithmvm vt constantem, logarithmicvm, linearem, nlog⁡nn \log n vel qvadraticvm classificare, et praedicere qvomodo tempvs eivs mvtetvr dvplicato nn.
  3. Tempvs exsecvtionis cvm std::chrono::steady_clock metiri et mensvram cvm praedictione comparare.
  4. Inter dvos algorithmos pro data magnitvdine datorvm eligere, electionem ordine incrementi ivstificando.

Operationes nvmerare

Altera qvaestio

Lectiones Circvitvs rectos designare et Recvrsio docvervnt qvomodo demonstretvr algorithmvm rectvm esse: evm terminari et eivs resvltatvm postcondicioni satisfacere. Atqvi lectio Algorithmi nvmerici dvo examina primalitatis aeqve recta ostendit, altervm circiter nn divisionibvs, altervm circiter n\sqrt{n}, et lectio Recvrsio dvos modos rectos compvtandi F30F_{30}, altervm 2 692 5372\,692\,537 vocationibvs, altervm 29 additionibvs. Qvod si ita est, rectitvdo ad eligendvm non svfficit: e dvobvs algorithmis rectis alter momento respondere potest, alter non finire anteqvam responsvm intersit. Altera igitvr qvaestio qvae algorithmo ponitvr est qvanti constet.

Svmptvs horologio metiri possemvs, et sectio qvarta id faciet. Sed tempvs vnivs exsecvtionis pendet a machina, a compilatore, ab eivs optionibvs et ab eo qvod compvtatrvm eodem tempore agit; ex eo nihil de algorithmo in alia machina seqvitvr. Qvod a nvllo horvm pendet est nvmervs gradvvm qvos algorithmvs facit. Ex qvo seqvitvr prima hvivs lectionis decisio: svmptvm nvmerando metiri, et horologivm ad nvmerationem confirmandam relinqvere.

Magnitvdo et operatio dominans

Omnes gradvs nvmerare (qvamqve additionem, qvamqve comparationem, qvodqve incrementvm indicis, qvemqve accessvm ad memoriam) molestvm et invtile esset, qvia fere omnes vnvm principalem proportione fixa comitantvr. Eligitvr igitvr operatio dominans: ea qvae saltem totiens exseqvitvr qvotiens qvaelibet alia, praeter factorem constantem, et qvae ideo omnes repraesentat. In svmma elementorvm vectoris est additio; in qvaerendo maximo, comparatio; in examine primalitatis, divisio. Nvmervs vicivm qvibvs exseqvitvr exprimitvr secvndvm magnitvdinem introitvs, qvae nn vocatvr: nvmervs elementorvm vectoris, nvmervs qvi examinatvr, nvmervs digitorvm.

Circvitvs simplex qvi vectorem nn elementorvm percvrrit et cvm vnoqvoqve fixam laboris qvantitatem facit operationem svam dominantem nn vicibvs exseqvitvr. Maximvm avtem vectoris non vacvi a primo elemento vt candidato incipit et cvm eo singvla cetera comparat: n−1n - 1 comparationes. Discrimen inter nn et n−1n - 1 vervm est, sed, vt in sectione tertia videbitvr, nihil eorvm qvae intersvnt mvtat.

Casvs pessimvs

Nonnvlli algorithmi non semper evndem nvmervm operationvm cvm datis eivsdem magnitvdinis exseqvvntvr. Inqvisitio valoris in vectore, qvem percvrrit donec evm inveniat, vnam tantvm comparationem facit si valor in prima positione est, et nn si abest. Vt de eivs svmptv loqvamvr, altera e dvabvs condicionibvs eligitvr, et electio vsitata est casvs pessimvs: nvmervs maximvs operationvm inter omnes introitvs magnitvdinis nn. Ratio eadem est ob qvam pactvm pro omnibvs introitibvs scribitvr qvi praecondicioni satisfacivnt: casvs pessimvs cavtio est, optimvs spes. Itaqve qvaesitio linearis nn comparationibvs in casv pessimo constat, et cvm haec lectio simpliciter «svmptvm» dicit, evm casvs pessimi dicit.

Circvitvs inclvsi

Lectio Circvitvs docvit qvomodo gyri dvorvm circvitvvm inclvsorvm nvmerentvr. Si interior semper mm gyros facit pro vnoqvoqve e nn exterioris, corpvs interivs n⋅mn \cdot m vicibvs exseqvitvr. Si interior ab exteriore pendet, ordine per ordinem svmmatvr. Casvs qvi in collectionibvs tractandis saepissime occvrrit est omnivm parivm: qvodqve elementvm cvm singvlis seqventibvs comparare, vt cvm qvaeritvr an vector repetita habeat.

Programma in C++
#include <print>​int main(){    for (int n{10}; n <= 10'000; n *= 10) {        long long comparisons{0};        for (int i{0}; i < n; ++i) {            for (int j{i + 1}; j < n; ++j) {                ++comparisons;            }        }        std::println("n = {:>6}: {:>10} comparationes; n(n - 1)/2 = {}",                     n, comparisons, static_cast<long long>(n) * (n - 1) / 2);    }}
Exitvs
n =     10:         45 comparationes; n(n - 1)/2 = 45n =    100:       4950 comparationes; n(n - 1)/2 = 4950n =   1000:     499500 comparationes; n(n - 1)/2 = 499500n =  10000:   49995000 comparationes; n(n - 1)/2 = 49995000

Nvmerator locvm tenet comparationis qvam algorithmvs vervs faceret. In gyro ii exterioris, interior a i+1i + 1 ad n−1n - 1 it et n−1−in - 1 - i gyros facit; itaqve svmma est (n−1)+(n−2)+⋯+1+0(n - 1) + (n - 2) + \cdots + 1 + 0, svmma lectionis Circvitvs:

∑i=0n−1(n−1−i)=n(n−1)2\sum_{i=0}^{n-1} (n - 1 - i) = \frac{n(n - 1)}{2}

Exitvs formvlam pro qvaqve magnitvdine confirmat. Nvmerator est long long qvia, ab nn circiter sexaginta qvinqve milivm, nvmervs parivm maximvm ipsivs int (in hac machina 32 bitorvm) svperat, et formvla eadem de cavsa post conversionem mvltiplicat: nvmerator algorithmi qvadratici mvlto ante data exvndat.

Iam animadvertatvr qvod sectio tertia generalizabit: mvltiplicato nn per 10, comparationes circiter per 100 mvltiplicantvr. Cvm decem datis, 45 comparationes; cvm decem milibvs, fere qvingenties centena milia.