Իրականացման խնդիրներ
Երբ աշխատում ենք ալգորիթմների և տվյալների կառուցվածքների հետ, մարդիկ հաճախ մտածում են, թե դրանք շատ բարդ բաներ են: Իրականում, շատ դեպքերում դրանք բավական պարզ ու ինտուիտիվ են: Միակ բանը, որ անհրաժեշտ է դրանք հասկանալու համար, որոշ քանակի գործնական փորձն է։ Դա կօգնի զգալ, թե իրականում ինչպես են ալգորիթմները աշխատում:
Երբ ուսումնասիրում ենք տարբեր խնդիրներ ու վարժություններ, պարզ է դառնում, որ կարելի է դրանք խմբավորել մի քանի բաժիններով և դրանք միասին դիտարկել: Շատ խնդիրներ ունեն ընդհանուր բնութագրեր, որոնք թույլ են տալիս կիրառել միևնույն ալգորիթմները ողջ խմբի խնդիրների համար:
Այդ խմբերից մեկը հենց իրականացման խնդիրներն են: Այդպիսի խնդիրներում լուծման քայլերը սովորաբար նկարագրված են հենց խնդիրի պայմանում: Այսինքն, այն գործողությունները, որոնք ծրագիրը պետք է կատարի, հասկանալի են դառնում հենց հանձնարարության մեջ: Ծրագրավորողի խնդիրն է օպտիմալ ձևով իրագործել այդ քայլերը և ստանալ ցանկալի արդյունքը: Պետք է նշել, որ որքան էլ քայլերը նկարագրված լինեն, դրանք անմիջապես իրագործելը միշտ չէ, որ այնքան էլ հեշտ է:
Առաջադրանք - Գտնել առաջին բաց թողնված թիվը
Մուտքում տրված են 1-ից
n բոլոր թվերը բացի մեկից։ Ձեզ խնդրում են գտնել բաց թողնված թիվը։Մուտք
Մուտքի առաջին տողում տրված է մեկ բնական թիվ՝
n-ը (2 ≤ n ≤ 100 000)։Մուտքի երկրորդ տողում տրված են
n-1 բացատով առանձնացված բնական թվեր (1 ≤ ≤ n)։Ելք
Ծրագիրը պետք է տպի բաց թողնված թիվը
Օրինակներ
Մուտք | Ելք |
4
3 4 1 | 2 |
3
2 1 | 3 |
Բարդություն և Big նշանակումը
Թեև վերը ներկայացված խնդիրը կարող է շատ հեշտ թվալ, պարզ լուծումը բավարար արագ չի աշխատի և բոլոր թեստերը չի անցնի։
Պարզ մոտեցումը կարող է լինել հետևյալը. կարդում ենք մուտքագրված տարրերը և պահում դրանք ցուցակի կամ զանգվածի մեջ, որից հետո կարող ենք անցնել 1-ից
n բոլոր թվերով և ստուգենք, թե արդյո՞ք թիվը գտնվում է մուտքագրված զանգվածի մեջ, թե՞ ո՛չ։ Եթե չի գտնվում՝ նշանակում է գտել ենք պատասխանը.n = int(input())
a = [int(ai) for ai in input().split()]
for i in range(1, n + 1): # n գործողություն
if i not in a: # n գործողություն (անցնում է բոլոր տարրերով)
print(i) # Գտանք լուծումը!Այս ալգորիթմը իրականում բավական դանդաղ է: Այն անցնում է 1-ից
n բոլոր թվերով և յուրաքանչյուր թվի համար ստուգում է արդյո՞ք այն list-ի մեջ է, թե՞ ոչ: Ստուգման գործողությունը գծային է (linear), որովհետև ծրագիրը ստիպված է հերթականությամբ անցնել list-ի բոլոր տարրերով, հասկանալու համար, կա՞ արդյոք տվյալ թիվը, թե՞ ոչ։ Արդյունքում, ընդհանուր գործողությունների քանակը ստացվում է մոտավորապես : Արտաքին ցիկլը կատարում է n քայլ, իսկ թե i թիվը կա զանգվածի մեջ, ստուգվում է ևս n քայլով։ Փաստորեն ընդհանուր առմամբ վատագույն դեպքում ունենում ենք ~ գործողություն:💻
Մեր համակարգիչները մեկ վայրկյանում կարող են կատարել մոտ 10-100 միլիոն գործողություն: Հետևաբար, եթե խնդիրն ունի 1 վայրկյան ժամանակի սահմանափակում (ինչն ընդունված է ալգորիթմական խնդիրներում), ապա պետք է փորձենք չգերազանցել 100 միլիոն գործողությունը:
Դիտարկենք վերը նշված խնդիրը, որտեղ
n-ը կարող է հասնել մինչև 100,000: Այդ դեպքում ստացվում է մոտ 10 միլիարդ (), որը սովորական համակարգչով աշխատացնելիս կարող է տևել մոտ 100 վայրկյան: Հաշվի առնելով, որ խնդրի ժամանակի սահմանափակումը 1 վայրկյան է, ակնհայտ է, որ պետք է գտնենք ավելի օպտիմալ լուծում:Big նշանակումը
Big O-ն ցույց է տալիս ալգորիթմի աճի վերին շեմը մուտքի չափից կախված: Այն մոտավորապես ցույց է տալիս, թե քանի գործողություն կարող է իրականացնել ալգորիթմը, երբ մուտքի չափը մեծանում է:
Վերոնշյալ օրինակում մենք հաշվեցինք, որ ալգորիթմը կատարում է մոտ
~ օպերացիա։ Ուստի նրա բարդությունը կարելի է նշել որպես :Մենք այս ամենի մասին դեռ ավելի մանրամասն կխոսենք դասընթացի ընթացքում՝ և՛ ինտուիտիվ տեսանկյունից, և՛ ավելի ֆորմալ տեսանկյունից:
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB