Tommelfingerreglen 10^8
Sæt antal operationer i forhold til tidsgrænsen
Tommelfingerreglen 10^8 er en gratis Forberedelse til kodeinterviews-lektion på CoddyKit. Dette er lektion 2 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.
Det magiske budget
En typisk online-dommer kører omkring 10^8 simple operationer i sekundet. Det tal er dit forbrugsbudget for hele programmet. 💡
Fra trin til sekunder
Gang dit antal operationer med arbejdet pr. trin, og sammenlign derefter med tidsgrænsen. Hvis trinene holder sig inden for budgettet, går løsningen sandsynligvis igennem.
Lineær tid er billig
Et O(n)-gennemløb af n = 10^6 er kun en million trin, langt under budgettet. Lineære løsninger går næsten altid komfortabelt igennem.
n log n er sikkert
For n = 10^6 kræver en sortering med O(n log n) omkring 2 gange 10^7 trin. Det er stadig langt inden for budgettet på ét sekund, så sortering er sjældent flaskehalsen.
Kvadratisk tid har en grænse
En tilgang med O(n^2) rammer budgettet omkring n = 10^4, hvor den koster 10^8 trin. Derefter begynder kvadratisk tid at overskride tidsgrænsen.
Kubisk tid fungerer kun ved små n
En løsning med O(n^3) overlever kun op til omkring n = 500. Når du opløfter det i tredje, når du omtrent 10^8 trin, som er budgetgrænsen.
Eksponentiel tid fungerer kun ved små n
O(2^n) fordobles for hvert trin, så det fungerer kun for meget små n omkring 20 til 25. Derefter eksploderer antallet af operationer forbi 10^8.
Python har en omkostning
Python er langsommere pr. trin, så regn med, at budgettet snarere er tættere på 10^7 for stramme løkker. Vær konservativ, når begrænsningerne ser kritiske ud.
Husk den skjulte konstant
Reglen om 10^8 tæller simple trin. Tungt arbejde inde i en løkke, f.eks. opbygning af strenge, tilføjer en konstant faktor, som reducerer dit reelle budget.
Læs tidsgrænsen
Tidsgrænsen er ofte 1 eller 2 sekunder. En grænse på 2 sekunder fordobler omtrent dit budget og giver lidt mere luft.
Estimér før du skriver
Sæt altid n ind i din kompleksitetsformel, og sammenlign først med 10^8. Dette hurtige rimelighedstjek sparer dig for at kode en håbløs løsning.
Hurtigt tjek
Brug reglen om 10^8 i praksis.
Opsummering
Du kan nu omsætte operationer til tid: omtrent 10^8 i sekundet. Lineær tid og n log n er sikre, kvadratisk tid har en grænse omkring 10^4, og du tjekker det før kodning. ✅
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 “Tommelfingerreglen 10^8” gratis?
Ja — hele teksten til “Tommelfingerreglen 10^8” 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 “Tommelfingerreglen 10^8”?
Sæt antal operationer i forhold til tidsgrænsen 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 2 af 4.
Hvor lang tid tager lektionen “Tommelfingerreglen 10^8”?
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
- Optælling af operationer med Big-O
- Tommelfingerreglen 10^8
- Læs begrænsningerne, og vælg kompleksitet
- Hvorfor TLE opstår, og hvordan du opdager det