Algoritma izpildes laika novērtēšana – Darbs ar laika sarežģītību (time complexity)
Šajā rakstā jūs izpētīsiet izstrādātu piemēru Python rakstītam koda fragmentam, kā arī to, kā jūs to novērtētu, izmantojot Big-O apzīmējumu.
[!]
Lietojumprogrammas veiktspējas novērtēšana nodrošina, ka uzrakstītais kods ir labs un atbilst mērķim. Jautājums ir, kā mēs novērtējam efektivitāti? Mērot elektrību, mēs izmantojam kilovatstundas, kas nozīmē, cik kilovatu ierīce patērēs, ja tā darbosies stundu. Ierīce ne vienmēr darbosies stundu, un tai var būt dažādas prasības atkarībā no izmantotā iestatījuma, tas ir vairāk vispārīgs izmaksu novērtēšanas noteikums.
Novērtējot kodēšanas risinājumus, tiek izmantots Big-O apzīmējums. Tātad Big-O apzīmējums ir koda novērtēšanas kilovatstunda. To var izmantot, lai izmērītu, cik daudz laika koda daļa aizņems vai cik daudz vietas tas aizņems atmiņā. Ne visi procesori darbosies ar tādu pašu ātrumu, tāpēc tā vietā, lai noteiktu lietojumprogrammas laiku, jūs uzskaitāt lietojumprogrammas iniciēto instrukciju skaitu.
Kurš mērījums atspoguļo ātrāko iespējamo kāda koda izpildi?
Izpētīsim, kurš mērījums atspoguļo ātrāko iespējamo kāda koda izpildi.
O(1)
Jūs izmantojat konstanta laika algoritmu, kura aprēķināšanai nepieciešams O(1) (O-of-one) laiks. Tas nosaka, ka uzdevuma pabeigšanai būs nepieciešams tikai viens aprēķins. Piemērs tam ir vienuma drukāšana no masīva.
# masīvs ar 5 numuriem
array = [0,1,2,3,4]
# izgūt numuru atrast rādītāja vietā 3
print(array[3]) Šajā gadījumā neatkarīgi no tā, cik vērtību masīvā ir, pieejai ir Big-O no 1. Tas nozīmē, ka šī koda palaišana tiek uzskatīta par O(1).
O(n)
Tālāk izpētīsim O(n) piemēru. Ņemot to pašu masīvu, tiek uzrakstīts if paziņojums, kas meklē skaitli 5. Lai noteiktu, ka 5 nav, tam ir jāpārbauda katrs masīva vienums.
# Masīvs ar 5 numuriem
array = [0,1,2,3,4]
if 5 in array:
print("piecinieks ire atrasts!")# Masīvs ar 10 numuriem
array = [0,1,2,3,4,6,7,8,9,10]
if 5 in array:
print("Piecinieks ir atrasts!")O(log n)
Šī meklēšana ir mazāk intensīva nekā O(n), bet vairāk darba nekā O(1). O(log n) ir logaritmiska meklēšana, un tā palielināsies, pievienojot jaunas ievades, taču šīs ievades piedāvā tikai nelielu pieaugumu. Lielisks piemērs tam ir binārā meklēšana. Binārā meklēšana būs aplūkota sīkāk vēlāk šo rakstu sērijā.
Tagad iedomājieties, ka spēlējat minēšanas spēli ar šādiem norādījumiem:
- pārāk augsts,
- pārāk zems
- vai pareizi.
Jums ir dots diapazons no 100 līdz 1. Jūs varat izlemt sistemātiski risināt problēmu. Pirmkārt, jūs minējāt 50 — pārāk augsts. Tātad, jūs minējāt 25 — kas ir pārāk augsts. Pēc tam varat izvēlēties 12 vai 13. Šeit notiek tas, ka ar katru minējumu jūs uz pusi samazināt meklēšanas laukumu.
Tātad, lai gan šīs funkcijas ievade bija 100, izmantojot binārās meklēšanas pieeju, jums vajadzētu atrast atbildi mazāk nekā 5 vai 6 minējumos. Šim risinājumam laika sarežģītība būtu O(log n). Pat ja n (ievadīto skaitļu diapazons) ir desmit reizes lielāks. Tas neprasīs desmitreiz vairāk minējumu.
Šeit ir šo masīva darbību sadalījums.
array = [0,1,2,3,4,6,7,8,9,10]
print("##Pirmais solis")
print("Masīvs")
print(array)
midpoint = int(len(array)/2)
print("Viduspunkts pirmajā solī ir: " , array[midpoint])
print()
print("##Otrais solis")
array = array[:midpoint] # 6 is the midpoint of the array
print("Masīvs")
print(array)
# izpildot šo rindu parādīsies skaitļi, kas palikuši pārbaudei
# vai 5 < 3
# nē
# tātad atmetam kreiso pusi
# tātad masīvs tiek sadalīts uz pusēm vēlreiz
midpoint=int(len(array)/2)
print("Viduspunkts ir: ", array[midpoint])
print()
print("##Trešais solis")
array = array[midpoint:] # tātad masīvs tiek sadalīts uz pusēm viduspunktā
print(array)
# pārbaudiet viduspunktu
midpoint=int(len(array)/2)
print("Viduspunkts ir: " , array[midpoint])
# vai 4 < 5
# jā skaties pa labi
print()
print("##Ceturtais solis")
print(array[midpoint:])
# pārbaudiet viduspunktu
array = array[midpoint:] # tātad masīvs tiek sadalīts uz pusēm viduspunktā
midpoint=int(len(array)/2)
print()
print("##Piektie solis")
array = array[midpoint:]
print(array)
print("ir tikai viena vērtība, ko pārbaudīt un tā nav 5")Iznākums būtu šāds:
##Pirmais solis
Masīvs
[0, 1, 2, 3, 4, 6, 7, 8, 9, 10]
Viduspunkts pirmajā solī ir: 4
##Otrais solis
Masīvs
[0, 1, 2, 3, 4]
Viduspunkts ir: 1
##Trešais solis
[3, 4]
Viduspunkts ir: 4
##Ceturtais solis
[4]
##Piektie solis
ir tikai viena vērtība, ko pārbaudīt un tā nav 5Jūs ievērosiet, ka, lai noteiktu, vai ir 5, bija jāveic 5 darbības. Tas ir big-Orādītājs O(5). Jūs varat redzēt, ka tas ir lielāks par O (1), bet mazāks par O (n). Tagad, kas notiek, ja masīvs tiek paplašināts līdz 100? Meklējot skaitli masīvā ar 10, vajadzēja 5 minējumus. Aplūkojot masīvu 100, nebūs jāveic 50 minējumi; tas aizņems ne vairāk kā 10. Tāpat, ja sarakstu pagarinās līdz 1000, minējumi palielināsies tikai līdz 15-20.
No tā mēs varam redzēt, ka tas nav O(1), jo atbilde nav tūlītēja. Tas nav big-O(n), jo minējumu skaits nepalielinās līdz ar masīva lielumu n. Tātad šeit tiek teikts, ka sarežģītība ir O(log(n)).
Lai iegūtu plašāku ieskatu par to, kā žurnāla vērtības ir tikai pakāpenisks pieaugums, skatiet žurnāla tabulu līdz 100 000 000. Šis objektīvs parāda, ka O(log n) ir tikai minimālas apstrādes izmaksas. Veicot bināro meklēšanu masīvā ar jebkurām n vērtībām, sliktākajā gadījumā vienmēr tiks veikts žurnāla vērtību kolonnā atrastais aprēķinu skaits.
O(n^2)
O(n^2) ir smags aprēķins. Šī ir kvadrātiskā sarežģītība, kas nozīmē, ka darbs tiek dubultots katram masīva elementam. Lielisks veids, kā to vizualizēt, ir ņemt vērā, ka jums ir dažādi masīvi. Saskaņā ar iepriekšējo piemēru, izpētīsim šādu kodu:
new_array=[] # masīvs, lai glabātu visus rezultātus
# masīvs ar pieciem skaitļiem
array = [0,1,2,3,4]
for i in range(len(array)): # masīvam ir pieci vērtības, tāpēc n=5
for j in range(len(array)): # joprojām tas pats masīvs, tāpēc n=5
new_array.append(i*j) # katrs aprēķins tiek saglabāts šeit
print(len(new_array)) # cik liels ir šis jaunais masīvs?tātad iznākums būs 25 !
Pirmā cilpa būs vienāda ar ievadīto elementu skaitu n. Otrajā cilpā tiks apskatīts arī ievades elementu skaits, n. Tādējādi var teikt, ka šīs pieejas izpildes vispārējā sarežģītība ir n*n, kas ir n^2 (n-kvadrātveida). Lai uzzinātu, cik aprēķinu ir veikts, jums ir jāizdrukā, cik reižu n tika izmantots cilpā, kā norādīts tālāk.
n = 5 #masīva lielums
print(n*n) # cik liels ir ši jaunais masīvs ? Ja zināt, ka masīvā ir 25 elementi, tad saprotat Big-O notācijas aprēķināšanas principus. Lai tālāk pārbaudītu savas zināšanas, cik aprēķinu būtu nepieciešams, ja n = 6? Tas nozīmē, ka masīvam bija 6 vērtības? Atbilde ir 6 x 6, tātad 36.
Problēmas vizuālais attēlojums
Zemāk ir grafisks attēlojums tam, kā n ir saistīta ar veikto aprēķinu skaitu.
Kā redzat, labākais laiks, uz kuru tiekties, ir O(1); O(log n) joprojām ir izcils. O(n) ir labi, un O(n^2) nav lieliski.
Sliktākais gadījums, labākais gadījums un vidējais gadījums
Protams, ne vienmēr ir iespējams pateikt, cik ilgi būs nepieciešama pieeja. Aplūkojot sākotnējās cilpas piemēru, tika meklēts elements, kura nebija. Var teikt, ka cilpas meklēšana prasa O(n) reizes, taču tas var ne vienmēr notikt.
Apsveriet, ka meklētais vienums ir pirmais masīvā. Tad atdeve būs diezgan laba O(1) laikā! Sniegtajā piemērā katrs vienums ir jāmeklē, pirms tiek noteikts, ka tā nebija: O(n) laiks. Vidējais gadījums būtu tāds, ka tas atrodas ap cilpas vidu O(n/2). Novērtējot pieeju, tiek izmantotas trīs definīcijas:
- labākais gadījums,
- sliktākais gadījums un
- vidējais gadījums.
Secinājums
Šajā rakstā tika ieviests laika jēdziens saistībā ar sarežģītību, un jūs izpētījāt izstrādātu piemēru Python rakstītam koda fragmentam. Jūs arī izpētījāt, kā jūs to novērtētu, izmantojot Big-O notāciju.
Labs jautājums, kas jāuzdod sev pirms darba sākšanas, ir “cik aprēķinu izmanto mans risinājums un vai ir labāks veids?” Tagad, kad zināt, kā izmantot metriku, lai novērtētu konkrētas problēmas risinājumu, varat sākt domāt par tās efektivitāti attiecībā uz laika sarežģītību.
Atbildēt
Lai komentētu, jums jāpiesakās sistēmā.