od stdhoom » 21. 4. 2015 20:02
Ahoj,
prosim o pomoc s príkladem:
Pracujete s databazi, ktera obsahuje informace o studentech a studijnich oborech. Kazdy student studuje prave jeden studijni obor. Kazdy studijni obor muze studovat vice studentu. Rekneme, ze dva studenti jsou spoluzaci, prave kdyz studuji stejny studujni obor.
Vasim ukolem je zjistit, zda v souboru N studentu existuje skupina alespon N/2 spoluzaku, tj. studentu studujicich stejny studijni obor. Problem je, ze jediny databazovy dotaz, ktery k tomu muzete vyuzit, je dotaz na dva studenty; jako odpoved obdrzite pouze informaci zda jsou anebo nejsou spoluzaci.
Navrhnete algoritmus, ktery nalezne pozadovanou odpoved a pritom pocet provedenych dotazu bude O(N log N). Pri navrhu algoritmu pouzijte techniku rozdel a panuj.
Nejsem schopen dosahnout slozitost nlogn
Ahoj,
prosim o pomoc s príkladem:
Pracujete s databazi, ktera obsahuje informace o studentech a studijnich oborech. Kazdy student studuje prave jeden studijni obor. Kazdy studijni obor muze studovat vice studentu. Rekneme, ze dva studenti jsou spoluzaci, prave kdyz studuji stejny studujni obor.
Vasim ukolem je zjistit, zda v souboru N studentu existuje skupina alespon N/2 spoluzaku, tj. studentu studujicich stejny studijni obor. Problem je, ze jediny databazovy dotaz, ktery k tomu muzete vyuzit, je dotaz na dva studenty; jako odpoved obdrzite pouze informaci zda jsou anebo nejsou spoluzaci.
Navrhnete algoritmus, ktery nalezne pozadovanou odpoved a pritom pocet provedenych dotazu bude O(N log N). Pri navrhu algoritmu pouzijte techniku rozdel a panuj.
Nejsem schopen dosahnout slozitost nlogn