Új hozzászólás Aktív témák

• #6274 sztanozs veterán Hunmugli #6272

  Új Válasz 2016-09-08 13:43:03 #6274

  Új hozzászólás

  Összes hozzászólása itt Válaszok az összes hozzászólására itt Válaszok erre a hozzászólásra

  Privát üzenet küldése

  

  sztanozs

  veterán

  válasz Hunmugli #6272 üzenetére

  Mekkora a legnagyobb prím, amit tárolni szeretnél?

• #6273 PumpkinSeed addikt Hunmugli #6272

  Új Válasz 2016-09-08 10:44:20 #6273

  Új hozzászólás

  Összes hozzászólása itt Válaszok az összes hozzászólására itt Válaszok erre a hozzászólásra

  Privát üzenet küldése

  

  PumpkinSeed

  addikt

  válasz Hunmugli #6272 üzenetére

  Ez nem egy túl jó megoldás, ugyanis a prím mennyiségének növekedésével jelentősen nő a műveleti idő is, ugyanis minden szám vizsgálatakor megnézed az összes tárolóban lévő prímet. Ebben az esetben n x m művelet fog végrehajtódni ahol az n a vizsgálandó számok mennyisége és m a tömbben lévő prímek mennyisége. Tegyük fel, hogy 100.000 számot akarsz vizsgálni és 40.000 prím van a tömbben (amit amúgy kézzel kellene felvinned) így 4.000.000.000 művelet kellene ahhoz, hogy 100.000 számot megvizsgálj. Ezek most csak számok, de ez túl sok művelet egy ilyen egyszerű feladathoz.

  Ezzel szemben kikukáztam a szita bonyolultságát ami Prim(N)=P(N), ami azt jelenti, hogy ha van N prímszámod akkor N művelet alatt oldja meg. Ami azt jelenti, hogy 100.000 szám esetén ~100.000 műveletből megkeresi őket szóval 40.000x gyorsabb mint az előző megoldás. Ezt amúgy constans complexity-nek hívják.

Új hozzászólás Aktív témák