Optimális esetben time és space complexity? C++
Ennél a feladatnál mi optimális megoldásnál a time és space complexity?
Kapok egy max 200 000 elemű 32 bites integer tömböt és minden elemet össze kell szorozni az (index szerint) utána következő elemekkel és a szorzatok összegét visszaadni modulo 1000000007.
Pl ha 2 4 7 van a tömbben akkor ezt az értéket kell visszaadni:
(2*4 + 2*7 + 4*7) % 1000000007 = 50
A 2 után a 4 és a 7 áll tehát azokkal kell összeszorozni, a 4 után pedig csak a 7 (és a 7 után pedig semmi).
Ha végig megyek minden párokon az ugye N^2 lenne de itt nem minden páron megyek végig mert az elemeket csak az utánuk következővel rakom párba. Ez ettől még N^2? Vagy van ennél jobb megoldás? A space complexity pedig O(1)?
Nem megoldásra vagyok kíváncsi (arra megpróbálok rájönni magamtól) csak a time és space complexityre.
válasza:Mert minden elemet más értékkel kell összeszorozni.
A példában pl. a 2-t 11-el, a 4-et pedig 7-el. Ezeknek az értékeknek valahol meg kell lennie, nem?
válasza:Összeadod a számokat és amikor végigmész a cikluson, akkor mindig kivonod az aktuálisat.
Pl: 1 2 3 4 5
Összeg: 15
első lépés:
- összegből kivonod az aktuálisat: 14
- eredmény változoba beleteszed az 1*14-et
második lépes:
- összegből kivonod az azkuálisat: 12
- eredmény változoba beleteszed az 2*12-t
Azért ez eélg triviális, nem? Nem kell semmilyen más értéknek meglennie sehol.
De egyébként a fenti módtól eltekintve a sima négyzetes megoldás is alapból O(1) space, 2 egymásba ágyazott ciklus ami mindig csak hozzáadja a szorzatokat az addigi összeghez. Tehát nem értem a problémád az O(1) space miatt, hiszen triviális.
válasza:*picit javítanám magam...
nem "az eredmény változoba beleteszed", hanem
"az eredmény változóhoz hozzáadod".. aminek a kezdeti értéke 0.
majd a legvégén modulo... vagy közben minden lépésnél.. ahogy jól esik vagy ahoyg elfér a változóban a szám:)
válasza:Valóvan kétszer kell végigmenni a tömbön, de az még mindig O(n) time.
Az összeg valóban tulcsordulhat, mint ahogy a négyzetes algoritmusnál is. De hát megfelő méretű változó kell és kész. Viszont ez még midig csak kb 2x annyni bit, mint egy szám mérete, ami még mindig O(1). (Nem függ a tömb méretétől)
Tehát pl. N darab 32 bites számhoz kell pár (konstans, kevés) darab 64 bites szám.
De egy 64 bites long long-ba pl. csak 2 int összege fér bele, nem? Akkor hogy adjak össze N darabot?
Nem értem hogy érted, hogy csak pár darab 64 bites szám kell.
válasza: válasza:2-es vagyok, nem kell kétszer végig menni a tömbön.
Küldtem megoldást privátban.
További kérdések:
Minden jog fenntartva © 2024, www.gyakorikerdesek.hu
GYIK | Szabályzat | Jogi nyilatkozat | Adatvédelem | Cookie beállítások | WebMinute Kft. | Facebook | Kapcsolat: info(kukac)gyakorikerdesek.hu
Ha kifogással szeretne élni valamely tartalommal kapcsolatban, kérjük jelezze e-mailes elérhetőségünkön!