Den greedy tankegang
Vælg det bedste trin, og se aldrig tilbage
Den greedy tankegang er en gratis Forberedelse til kodeinterviews-lektion på CoddyKit. Dette er lektion 1 af 4. Du kan læse hele lektionen gratis nedenfor — og derefter øve dig praktisk i browseren med en indbygget kodeeditor og en AI-vejleder, der er tilgængelig døgnet rundt. Den er en del af læringsforløbet i Forberedelse til kodeinterviews, og dine fremskridt synkroniseres på tværs af nettet og CoddyKit-appen. Forberedelse til kodeinterviews-kurset indeholder 4 lektioner i alt.
Hvad grådig betyder
En grådig algoritme bygger et svar trin for trin, idet den altid vælger den mulighed, der ser bedst ud lige nu, uden senere at omgøre valget. ⚡
Vælg det bedste trin
Hver gang spørger du om én ting: Hvilken enkelt mulighed hjælper mest lokalt? Du vælger den og går videre til den næste beslutning.
Se aldrig tilbage
En grådig algoritme binder sig til et valg og går aldrig tilbage. I modsætning til backtracking udforsker den ikke andre veje, og det er netop det, der gør den så hurtig.
Hvorfor grådige algoritmer er hurtige
Fordi den træffer én beslutning pr. trin, kører en grådig algoritme normalt i O(n) eller O(n log n) efter sortering. Den hastighed er dens største fordel i konkurrencer.
Vanen med at sortere
De fleste grådige løsninger begynder med at sortere elementerne. Rækkefølgen viser, hvilket element der tydeligvis er det bedste valg på hvert trin.
items.sort(key=lambda x: x.cost)Egenskaben ved det grådige valg
Grådige algoritmer virker kun, når et lokalt bedste valg også indgår i et globalt optimalt svar. Det er egenskaben ved det grådige valg.
Det er ikke altid rigtigt
Det kan stadig mislykkes samlet set at vælge det bedste trin nu. Møntskifte med uregelmæssige møntværdier er et klassisk eksempel, hvor en grådig algoritme giver en forkert sum.
Bevis det eller afprøv det
Før du stoler på en grådig algoritme, skal du begrunde den med et ombytningsargument eller stressteste den mod en udtømmende løsning på små datasæt.
Ombytningsargumentet
I et ombytningsbevis bytter du det grådige valg ind i et optimalt svar og viser, at resultatet ikke bliver dårligere. Hvis det holder, er den grådige algoritme sikker.
En lille grådig løkke
Her er strukturen i næsten alle grådige algoritmer: sortér, og gennemløb derefter listen én gang, mens du tager det, der passer til din regel.
items.sort()
for x in items:
if fits(x):
take(x)Hvornår du skal vælge en grådig algoritme
Prøv en grådig algoritme, når en tydelig rækkefølge rangerer valgene, og én regel bliver ved med at vinde. Hvis valgene påvirker hinanden på indviklede måder, bør du i stedet overveje DP.
Hurtigt tjek
Du overvejer, om en grådig tilgang er til at stole på.
Opsummering
En grådig algoritme vælger det bedste lokale trin og ser aldrig tilbage, som regel efter først at have sorteret. Den er hurtig, men kun korrekt, når du kan bevise, at det grådige valg holder. 🚀
Lær Forberedelse til kodeinterviews med en AI-underviser — gratis
Skriv og kør rigtig kode i din browser, få øjeblikkelig hjælp fra en AI-underviser døgnet rundt, og fortsæt, hvor du slap, på web eller i appen.
- Kurser
- 90
- Lektioner
- 360
Ofte stillede spørgsmål
Er lektionen “Den greedy tankegang” gratis?
Ja — hele teksten til “Den greedy tankegang” kan læses gratis her på nettet. Hvis du vil øve dig interaktivt med en indbygget kodeeditor og en AI-vejleder døgnet rundt og få adgang til resten af Forberedelse til kodeinterviews-kurset, skal du opgradere til CoddyKit PRO. Forberedelse til kodeinterviews-kurset indeholder 4 lektioner i alt.
Hvad lærer jeg i “Den greedy tankegang”?
Vælg det bedste trin, og se aldrig tilbage Du øver dig i Forberedelse til kodeinterviews med praktisk kode, som du kører direkte i browseren, og en AI-vejleder døgnet rundt besvarer dine spørgsmål, mens du arbejder dig gennem lektionen.
Skal jeg have erfaring for at begynde på Forberedelse til kodeinterviews?
Der kræves ingen tidligere erfaring. Forberedelse til kodeinterviews på CoddyKit er tilrettelagt for både begyndere og øvede, så du kan starte her eller fra begyndelsen og lære i dit eget tempo. Dette er lektion 1 af 4.
Hvor lang tid tager lektionen “Den greedy tankegang”?
De fleste CoddyKit-lektioner tager cirka 5–10 minutter. Hver lektion er kort og interaktiv, så du gør løbende fremskridt og kan fortsætte, hvor du slap – på både web og app.
Kan jeg skrive og køre kode i denne Forberedelse til kodeinterviews-lektion?
Ja. Alle Forberedelse til kodeinterviews-lektioner har en indbygget kodeeditor, så du kan skrive og køre rigtig kode direkte i din browser og få øjeblikkelig feedback fra AI – uden lokal opsætning.
Alle lektioner i dette kursus
- Den greedy tankegang
- Aktivitetsudvælgelse efter tidligste afslutning
- Fraktionel knapsack efter forholdstal
- Opdag, når greedy fejler