Greedy-ajattelutapa
Valitse paras askel äläkä katso taaksepäin
Greedy-ajattelutapa on ilmainen Valmistautuminen ohjelmointihaastatteluihin-oppitunti CoddyKitissä. Tämä on oppitunti 1/4. Voit lukea koko oppitunnin alta ilmaiseksi ja harjoitella sen jälkeen käytännössä selaimessa sisäänrakennetulla koodieditorilla ja ympäri vuorokauden käytettävissä olevan tekoälytuutorin avulla. Oppitunti kuuluu Valmistautuminen ohjelmointihaastatteluihin-oppimispolkuun, ja edistymisesi synkronoituu verkon ja CoddyKit-sovelluksen välillä. Valmistautuminen ohjelmointihaastatteluihin-kurssilla on yhteensä 4 oppituntia.
Mitä ahneus tarkoittaa
Ahne algoritmi rakentaa vastauksen vaihe vaiheelta valitsemalla aina juuri nyt parhaalta vaikuttavan vaihtoehdon eikä peruuta valintojaan myöhemmin. ⚡
Valitse paras vaihe
Jokaisessa vaiheessa kysytään yksi asia: mikä yksittäinen vaihtoehto auttaa eniten paikallisesti? Valitse se ja siirry seuraavaan päätökseen.
Älä katso taaksepäin
Ahne algoritmi sitoutuu valintaansa eikä koskaan peruuta sitä. Toisin kuin peruutushaussa, se ei tutki muita polkuja, mikä tekee siitä niin nopean.
Miksi ahne algoritmi on nopea
Koska päätös tehdään kerran joka vaiheessa, ahneen algoritmin aikavaativuus on lajittelun jälkeen yleensä O(n) tai O(n log n). Tämä nopeus on sen suurin etu kilpailutehtävissä.
Lajittelutapa
Useimmat ahneet ratkaisut alkavat alkioiden lajittelulla. Järjestys paljastaa, mikä alkio on kussakin vaiheessa ilmeinen paras valinta.
items.sort(key=lambda x: x.cost)Ahneen valinnan ominaisuus
Ahne menetelmä toimii vain, kun paikallinen paras valinta kuuluu myös johonkin maailmanlaajuisesti parhaaseen ratkaisuun. Tätä kutsutaan ahneen valinnan ominaisuudeksi.
Se ei ole aina oikein
Parhaan vaihtoehdon valitseminen heti voi silti epäonnistua kokonaisuuden kannalta. Kolikkorahanvaihto parittomilla nimellisarvoilla on klassinen esimerkki tilanteesta, jossa ahne menetelmä tuottaa väärän summan.
Todista tai testaa
Ennen kuin luotat ahneeseen menetelmään, perustele se vaihtoargumentilla tai testaa sitä perusteellisesti pieniä syötteitä käsittelevää brute force -ratkaisua vasten.
Vaihtoargumentti
Vaihtotodistuksessa ahne valinta vaihdetaan optimaaliseen ratkaisuun ja osoitetaan, ettei tulos heikkene. Jos tämä pitää paikkansa, ahne menetelmä on turvallinen.
Pieni ahne silmukka
Tässä on lähes jokaisen ahneen ratkaisun rakenne: lajittele ja käy sitten lista kerran läpi valiten kaiken, mikä sopii sääntöön.
items.sort()
for x in items:
if fits(x):
take(x)Milloin ahnetta menetelmää kannattaa käyttää
Kokeile ahnetta menetelmää, kun selkeä järjestys asettaa vaihtoehdot paremmuusjärjestykseen ja yksi sääntö toimii jatkuvasti parhaiten. Jos valinnat vaikuttavat toisiinsa monimutkaisesti, harkitse mieluummin dynaamista ohjelmointia.
Pikatarkistus
Harkitset, voiko ahkeaan menetelmään luottaa.
Kertaus
Ahne menetelmä valitsee parhaan paikallisen vaihtoehdon eikä katso taaksepäin, yleensä ensin lajiteltuaan alkiot. Se on nopea, mutta oikein vain silloin, kun ahneen valinnan oikeellisuuden voi todistaa. 🚀
Opi Valmistautuminen ohjelmointihaastatteluihin tekoälytuutorin avulla — ilmaiseksi
Kirjoita ja suorita oikeaa koodia selaimessa, saa välitöntä apua tekoälytuutorilta ympäri vuorokauden ja jatka siitä, mihin jäit, verkossa tai sovelluksessa.
- Kurssit
- 90
- Oppitunnit
- 360
Usein kysytyt kysymykset
Onko oppitunti ”Greedy-ajattelutapa” ilmainen?
Kyllä – oppitunnin ”Greedy-ajattelutapa” koko tekstin voi lukea täällä verkossa ilmaiseksi. Jos haluat harjoitella interaktiivisesti sisäänrakennetulla koodieditorilla ja ympäri vuorokauden käytettävissä olevan tekoälytuutorin avulla sekä avata koko Valmistautuminen ohjelmointihaastatteluihin-kurssin, päivitä CoddyKit PROhon. Valmistautuminen ohjelmointihaastatteluihin-kurssilla on yhteensä 4 oppituntia.
Mitä opin oppitunnilla ”Greedy-ajattelutapa”?
Valitse paras askel äläkä katso taaksepäin Harjoittelet Valmistautuminen ohjelmointihaastatteluihin-aihetta koodilla, jonka suoritat suoraan selaimessa. Ympäri vuorokauden käytettävissä oleva tekoälytuutori vastaa kysymyksiisi oppitunnin aikana.
Tarvitsenko kokemusta aloittaakseni Valmistautuminen ohjelmointihaastatteluihin-opiskelun?
Aiempi kokemus ei ole tarpeen. CoddyKitin Valmistautuminen ohjelmointihaastatteluihin-oppimispolku sopii vasta-alkajista edistyneisiin, joten voit aloittaa tästä tai alusta ja edetä omaan tahtiisi. Tämä on oppitunti 1/4.
Kuinka kauan ”Greedy-ajattelutapa”-oppitunnin suorittaminen kestää?
Useimmat CoddyKitin oppitunnit kestävät noin 5–10 minuuttia. Jokainen oppitunti on lyhyt ja interaktiivinen, joten edistyt tasaisesti ja voit jatkaa siitä, mihin jäit – sekä verkossa että sovelluksessa.
Voinko kirjoittaa ja suorittaa koodia tällä Valmistautuminen ohjelmointihaastatteluihin-oppitunnilla?
Kyllä. Jokainen Valmistautuminen ohjelmointihaastatteluihin-oppitunti sisältää sisäänrakennetun koodieditorin, joten voit kirjoittaa ja suorittaa oikeaa koodia suoraan selaimessa ja saada välitöntä palautetta tekoälyltä – paikallista asennusta ei tarvita.
Kaikki tämän kurssin oppitunnit
- Greedy-ajattelutapa
- Aktiviteettien valinta aikaisimman lopun perusteella
- Murtolukureppu suhteen perusteella
- Huomaa, milloin greedy epäonnistuu