Van jobb megoldás erre a feladatra?

Rendezetlen tömbre szerintem ez egy egész jó algoritmus. Az aktuális elem mondjuk önmagát is ellenőrzi, tehát pl. a külső ciklusban a 3-at a belső ciklusban ezzel a hármassal is összehasonlítja, de lehet, hogy még így is kisebb erőforrásigényű, mint a belsőben átugornia az aktuális elemet.

Nagy tömbök esetén esetleg létre lehet hozni valami átmeneti adatstruktúrát, ahol azt jelzed, hogy ha egy elem kisebb, mint az aktuális, akkor azt már erre vonatkozóan legközelebb ugorja át, tehát visszafelé ne ellenőrizze. De ez csak akkor éri meg (talán), ha tényleg nagyon nagy tömbről van szó.

Az algoritmusod négyzetes komplexitást eredményez és belátható, hogy performancia szempontjából ez elég rossz.

Lineáris komplexitással is megoldható a dolog, én valahogy így csinálnám:

https://pastebin pont com/4gZtm5E1

(könnyen elképzelhető, hogy van jobb megoldás, nem agyaltam rajta sokat)

Összehasonlításképpen te 100 elemű tömbnél 10 000 elemet érintesz, 1 000 eleműnél már egy milliót és így tovább.

Ez a lineáris megoldás 100 elem esetén 200 elemet érint (+ konstans 101), 1 000 elem esetén 2 000-et (+ konstans 101) stb.

A space complexity ugye attól függ, hogy módosítható-e a bemeneti tömb. Mivel erről nem írtál semmit, így feltételeztem, hogy igen és így konstans a komplexitás. Ha nem módosítható a bemenet, akkor nyilván új tömbbe kéne írni az eredményt (ami lineáris komplexitáshoz vezetne).

Szerintem így gyorsabb nagyméretű bemenet esetén:

- létrehozod a kimeneti tömböt

- létrehozol egy 101 elemű int tömböt (0-100 lehet az érték), 0-kkal inicializálod

- bejárod a bemeneti tömböt és a számláló tömbben növeled az "bemenet[i]" indexű számlálókat

- még egyszer bejárod a bemeneti tömböt és minden iterációban összeadod az "bemenet[i]"-nél kisebb indexű elemeket a számláló tömbből; és ezt beteszed a kimeneti tömbbe

Ez O(n)-es, ha jól gondolom (a legrosszabb eset: n + n * 100 // a csupa 100 esete). A tiéd pedig O(n^2)-es.

Hasonló a logika, mint amit #5 írt, csak feltöltöm a számláló tömb üres indexeit a megelőző értékkel, ezzel megspórolva a későbbi iterációkat a számláló tömbön.

Tehát ha a bemenet mondjuk [1, 1, 5], akkor így fog kinézni a számláló tömb: [0, 2, 2, 2, 2, 7]

[1, 1, 5, 3] bemenet esetén: [0, 2, 2, 3, 3, 8]

Ezután a bemenet i indexéhez csak ki kell vennem a számláló tömb i - 1 indexét, mert az a megelőző elemek számával egyenlő.