Monet opiskelijat hämmentyvät ymmärtäessään ajan monimutkaisuuden käsitteen, mutta tässä artikkelissa selitämme sen hyvin yksinkertaisella esimerkillä.
K. Kuvittele 100 oppilaan luokkahuone, jossa annoit kynäsi yhdelle henkilölle. Sinun täytyy löytää se kynä tietämättä kenelle annoit sen.
Tässä on joitain tapoja löytää kynä ja mikä on O-järjestys.
- Päällä 2 ): Menet ja kysy luokan ensimmäiseltä henkilöltä, onko hänellä kynä. Lisäksi kysyt tältä henkilöltä muista 99 ihmisestä luokkahuoneessa, onko heillä kynä ja niin edelleen,
Tätä kutsumme O(n2). - Päällä): Jokaiselta opiskelijalta erikseen kysyminen on O(N).
- O(log n): Nyt jaan luokan kahteen ryhmään ja kysyn sitten: Onko se luokkahuoneen vasemmalla vai oikealla puolella? Sitten otan sen ryhmän ja jaan sen kahteen osaan ja kysyn uudelleen ja niin edelleen. Toista prosessia, kunnes jäljellä on yksi opiskelija, jolla on kynäsi. Tätä tarkoitat O(log n:llä).
Minun täytyy ehkä tehdä:
- The Päällä 2 ) etsii jos vain yksi oppilas tietää, kenen päällä kynä on piilotettu .
- The Päällä) jos yhdellä oppilaalla oli kynä ja vain he tiesivät sen .
- The O(log n) etsi jos kaikki oppilaat tiesivät , mutta kertoisi minulle vain, jos arvasin oikean puolen.
Ylempi O -> kutsutaan Iso - Oh joka on asymptoottinen merkintä. Muitakin on asymptoottisia merkintöjä Kuten theta ja Omega .
HUOMAUTUS: Olemme kiinnostuneita ohjelman toteuttamisen aikana saatujen panosten kasvusta ajan mittaan.
Onko algoritmin/koodin aika monimutkaisuus sama kuin koodin ajo-/suoritusaika?
Algoritmin/koodin aika monimutkaisuus on ei sama kuin tietyn koodin suorittamiseen tarvittava todellinen aika, mutta käskyn suorituskertojen määrä. Voimme todistaa tämän käyttämällä ajan käsky .
Esimerkiksi: Kirjoita koodi C/C++-kielellä tai millä tahansa muulla kielellä löytääksesi enimmäismäärän N-luvun välillä, missä N vaihtelee välillä 10, 100, 1000 ja 10000. Linux-pohjaisessa käyttöjärjestelmässä (Fedora tai Ubuntu) käytä alla olevia komentoja:
fibonacci-sarja vuonna v
Ohjelman kokoaminen: gcc program.c – o-ohjelma
Ohjelman suorittaminen: aika ./ohjelma
Saat yllättäviä tuloksia mm.
- Jos N = 10: saatat saada 0,5 ms aikaa,
- Jos N = 10 000: saatat saada 0,2 ms aikaa.
- Saat myös eri ajoitukset eri koneilla. Vaikka et saa samoja ajoituksia samalle koneelle samalle koodille, syynä tähän on nykyinen verkon kuormitus.
Joten voimme sanoa, että koodin suorittamiseen tarvittava todellinen aika riippuu koneesta (Käytätkö Pentium 1 tai Pentium 5) ja myös se ottaa huomioon verkon kuormituksen, jos koneesi on LAN/WAN-verkossa.
Mitä algoritmin aikakompleksisuudella tarkoitetaan?
Nyt herää kysymys, jos aika monimutkaisuus ei ole todellinen aika, joka tarvitaan koodin suorittamiseen, niin mikä se on?
Vastaus on:
Sen sijaan, että mittaisit todellista aikaa, joka tarvitaan jokaisen koodin lauseen suorittamiseen, Aika monimutkaisuus ottaa huomioon, kuinka monta kertaa kukin lause suoritetaan.
Esimerkki 1: Harkitse alla olevaa yksinkertaista koodia tulosta Hello World
C++ #include using namespace std; int main() { cout << 'Hello World'; return 0; } // This code is contributed by vikash36905.> C #include int main() { printf('Hello World'); return 0; }> Java import java.io.*; class GFG { public static void main(String[] args) { System.out.print('Hello World'); } } // This code is contributed by vikash36905.> Python 3 print('Hello World') # This code is contributed by akashish__> C# using System; public class GFG{ static public void Main (){ // Code Console.WriteLine('Hello World'); } } // This code is contributed by lokesh> Javascript console.log('Hello World') // This code is contributed by nilha72xi.> Lähtö
Hello World>
Aika monimutkaisuus: Yllä olevassa koodissa Hello World on painettu näytölle vain kerran.
Aika monimutkaisuus on siis vakio: O(1) eli joka kerta, kun koodin suorittamiseen tarvitaan vakioaika, riippumatta siitä, mitä käyttöjärjestelmää tai koneen kokoonpanoja käytät.
Aputila : O(1)
Esimerkki 2:
C++ #include using namespace std; int main() { int i, n = 8; for (i = 1; i <= n; i++) { cout << 'Hello World !!!
'; } return 0; } // This code is contributed by vikash36905.> C #include void main() { int i, n = 8; for (i = 1; i <= n; i++) { printf('Hello World !!!
'); } }> Java class GFG { public static void main(String[] args) { int i, n = 8; for (i = 1; i <= n; i++) { System.out.printf('Hello World !!!
'); } } } // This code is contributed by Rajput-Ji> Python 3 # Python code n = 8 for i in range(1, n + 1): print('Hello World !!!') # This code is contributed by lokesh> C# using System; public class GFG { public static void Main(String[] args) { int i, n = 8; for (i = 1; i <= n; i++) { Console.Write('Hello World !!!
'); } } } // This code contributed by Rajput-Ji> Javascript let i, n = 8; for (i = 1; i <= n; i++) { console.log('Hello World !!!'); }> Lähtö
Hello World !!! Hello World !!! Hello World !!! Hello World !!! Hello World !!! Hello World !!! Hello World !!! Hello World !!!>
Aika monimutkaisuus: Yllä olevassa koodissa Hello World!!! on vain painettu n kertaa näytöllä, koska n:n arvo voi muuttua.
Aika monimutkaisuus on siis lineaarinen: O(n) eli joka kerta koodin suorittamiseen tarvitaan lineaarinen aika.
Aputila: O(1)
Esimerkki 3:
C++ #include using namespace std; int main() { int i, n = 8; for (i = 1; i <= n; i=i*2) { cout << 'Hello World !!!
'; } return 0; } // This code is contributed by Suruchi Kumari> C #include void main() { int i, n = 8; for (i = 1; i <= n; i=i*2) { printf('Hello World !!!
'); } } // This code is contributed by Suruchi Kumari> Java class GFG { public static void main(String[] args) { int i, n = 8; for (i = 1; i <= n; i=i*2) { System.out.println('Hello World !!!'); } } } // This code is contributed by Suruchi Kumari> Python 3 n = 8 # for (i = 1; i <= n; i=i*2) { for i in range(1, n+1, 2): print('Hello World !!!') # This code is contributed by akashish__> C# using System; public class GFG{ static public void Main (){ // Code int i, n = 8; for (i = 1; i <= n; i=i*2) { Console.Write('Hello World !!!
'); } } } // This code is contributed by lokeshmvs21.> Javascript for (i = 1; i <= 8; i=i*2) { console.log('Hello World !!!'); } // This code is contributed by nilha7xi.> Lähtö
Hello World !!! Hello World !!! Hello World !!! Hello World !!!>
Aika monimutkaisuus: O(log2(n))
Aputila: O(1)
Esimerkki 4:
java char intC++
#include #include using namespace std; int main() { int i, n = 8; for (i = 2; i <= n; i=pow(i,2)) { cout << 'Hello World !!!
'; } return 0; } // This code is contributed by Suruchi Kumari> C #include #include void main() { int i, n = 8; for (i = 2; i <= n; i=pow(i,2)) { printf('Hello World !!!
'); } } // This code is contributed by Suruchi Kumari> Java import java.lang.Math; class GFG { public static void main(String args[]){ int i, n = 8; for (i = 2; i <= n; i=(int)Math.pow(i,2)) { System.out.println('Hello World !!!'); } } }> Python 3 n = 8 i = 2 for j in range(2,n+1): if(i>= n): break print('Hello World !!!') i *= i # Tämän koodin on tuottanut akashish__> C# using System; using System.Collections.Generic; public class GFG { static public void Main() { int i, n = 8; for (i = 2; i <= n; i = (int)Math.Pow(i, 2)) { Console.WriteLine('Hello World !!!'); } } } // This code is contributed by akashish__> Javascript for (let i = 2; i <= 8; i=Math.pow(i,2)) { console.log('Hello World !!!'); } // This code is contributed by nilha7xi.> Lähtö
Hello World !!! Hello World !!!>
Aika monimutkaisuus: O(log(log n))
Aputila: O(1)
Kuinka löytää algoritmin aika monimutkaisuus?
Katsokaamme nyt joitain muita esimerkkejä ja prosessia algoritmin aikamonimutkaisuuden löytämiseksi:
Esimerkki: Tarkastellaan mallikonetta, jolla on seuraavat tekniset tiedot:
- Yksi prosessori
- 32-bittinen
- Peräkkäinen suoritus
- 1 aikayksikkö aritmeettisille ja loogisille operaatioille
- 1 yksikköaika tehtävä- ja palautuslausekkeille
Q1. Etsi 2 luvun summa yllä olevasta koneesta:
Jokaisen koneen pseudokoodi kahden numeron lisäämiseksi on suunnilleen tällainen:
C++ // Pseudocode : Sum(a, b) { return a + b } #include using namespace std; int sum(int a,int b) { return a+b; } int main() { int a = 5, b = 6; cout< C Pseudocode : Sum(a, b) { return a + b }> Java // Pseudocode : Sum(a, b) { return a + b } import java.io.*; class GFG { public static int sum(int a, int b) { return a + b; } public static void main(String[] args) { int a = 5, b = 6; System.out.println(sum(a, b)); } } // This code is contributed by akashish__> Python 3 # Pseudocode : Sum(a, b) { return a + b } a = 5 b = 6 def sum(a,b): return a+b # function call print(sum(a,b))> C# // Pseudocode : Sum(a, b) { return a + b } using System; public class GFG { public static int sum(int a, int b) { return a + b; } static public void Main() { int a = 5, b = 6; Console.WriteLine(sum(a, b)); } } // This code is contributed by akashish__> Javascript // Pseudocode : Sum(a, b) { return a + b } function sum(a, b) { return a + b; } let a = 5, b = 6; console.log(sum(a, b)); // This code is contributed by akashish__> Lähtö
11>
Aika monimutkaisuus:
- Yllä oleva koodi kestää 2 aikayksikköä (vakio):
- yksi aritmeettisille operaatioille ja
- yksi palautusta varten. (yllä olevien sopimusten mukaisesti).
- Siksi summaoperaation suorittamisen kokonaiskustannukset ( ) = 1 + 1 = 2
- Aika monimutkaisuus = O(2) = O(1) , koska 2 on vakio
Aputila: O(1)
Q2. Etsi luettelon/taulukon kaikkien elementtien summa
Pseudokoodi sen tekemiseen voidaan antaa seuraavasti:
C++ #include using namespace std; int list_Sum(int A[], int n) // A->taulukko ja // n->elementtien lukumäärä taulukossa { int summa = 0; for (int i = 0; i<= n - 1; i++) { sum = sum + A[i]; } return sum; } int main() { int A[] = { 5, 6, 1, 2 }; int n = sizeof(A) / sizeof(A[0]); cout << list_Sum(A, n); return 0; } // This code is contributed by akashish__> C Pseudocode : list_Sum(A, n) // A->taulukko ja // n->elementtien lukumäärä taulukossa { summa = 0, kun i = 0 - n-1 sum = summa + A[i] paluusumma }> Java // Java code for the above approach import java.io.*; class GFG { static int list_Sum(int[] A, int n) // A->taulukko ja // n->elementtien lukumäärä taulukossa { int summa = 0; for (int i = 0; i<= n - 1; i++) { sum = sum + A[i]; } return sum; } public static void main(String[] args) { int[] A = { 5, 6, 1, 2 }; int n = A.length; System.out.println(list_Sum(A, n)); } } // This code is contributed by lokeshmvs21.> Python 3 # A function to calculate the sum of the elements in an array def list_sum(A, n): sum = 0 for i in range(n): sum += A[i] return sum # A sample array A = [5, 6, 1, 2] # Finding the number of elements in the array n = len(A) # Call the function and print the result print(list_sum(A, n))>
C# using System; public class GFG { public static int list_Sum(int[] A, int n) // A->taulukko ja // n->elementtien lukumäärä taulukossa { int summa = 0; for (int i = 0; i<= n - 1; i++) { sum = sum + A[i]; } return sum; } static public void Main() { int[] A = { 5, 6, 1, 2 }; int n = A.Length; Console.WriteLine(list_Sum(A, n)); } } // This code is contributed by akashish__> Javascript function list_Sum(A, n) // A->taulukko ja // n->alkioiden määrä taulukossa { olkoon summa = 0; for (olkoon i = 0; i<= n - 1; i++) { sum = sum + A[i]; } return sum; } let A = [ 5, 6, 1, 2 ]; let n = A.length; console.log(list_Sum(A, n)); // This code is contributed by akashish__> Lähtö
14>
Ymmärtääksesi yllä olevan koodin aikamonimutkaisuuden, katsotaan kuinka paljon aikaa kukin lause vie:
int list_Sum(int A[], int n) { int sum = 0; // cost=1 no of times=1 for(int i=0; i C Pseudocode : list_Sum(A, n) { total =0 // cost=1 no of times=1 for i=0 to n-1 // cost=2 no of times=n+1 (+1 for the end false condition) sum = sum + A[i] // cost=2 no of times=n return sum // cost=1 no of times=1 }> Java public class ListSum { // Function to calculate the sum of elements in an array static int listSum(int[] A, int n) { int sum = 0; // Cost = 1, executed 1 time for (int i = 0; i < n; i++) { // Cost = 2, executed n+1 times (+1 for // the end false condition) sum = sum + A[i]; // Cost = 2, executed n times } return sum; // Cost = 1, executed 1 time } // Main method for testing public static void main(String[] args) { int[] array = {1, 2, 3, 4, 5}; int length = array.length; int result = listSum(array, length); System.out.println('Sum: ' + result); } }> Python 3 def list_sum(A): sum = 0 for i in range(len(A)): sum = sum + A[i] return sum>
C# using System; class Program { // Function to calculate the sum of elements in a list static int ListSum(int[] A) { int sum = 0; // Initialize sum to 0 // Loop to iterate through the array elements for (int i = 0; i < A.Length; i++) { sum = sum + A[i]; // Accumulate the sum } return sum; // Return the calculated sum } // Driver code static void Main() { // Example usage int[] array = { 1, 2, 3, 4, 5 }; int result = ListSum(array); Console.WriteLine(result); } }> Javascript function listSum(A) { let sum = 0; // Initialize sum to 0 // Loop to iterate through the array elements for (let i = 0; i < A.length; i++) { sum = sum + A[i]; // Accumulate the sum } return sum; // Return the calculated sum } // Example usage let array = [1, 2, 3, 4, 5]; let result = listSum(array); console.log(result);> Siksi summaoperaation suorittamisen kokonaiskustannukset
Summa = 1 + 2 * (n+1) + 2 * n + 1 = 4n + 4 = C1 * n + C2 = O(n)
Siksi yllä olevan koodin aikamonimutkaisuus on Päällä)
Q3. Etsi matriisin kaikkien elementtien summa
Tässä tapauksessa monimutkaisuus on polynomiyhtälö (neliömatriisin toisen asteen yhtälö)
- Matriisi, jonka koko on n*n => Tsum = a.n 2 + b.n + c
- Koska Tsum on järjestyksessä n2, siksi Aika monimutkaisuus = O(n 2 )
#include using namespace std; int main() { int n = 3; int m = 3; int arr[][3] = { { 3, 2, 7 }, { 2, 6, 8 }, { 5, 1, 9 } }; int sum = 0; // Iterating over all 1-D arrays in 2-D array for (int i = 0; i < n; i++) { // Printing all elements in ith 1-D array for (int j = 0; j < m; j++) { // Printing jth element of ith row sum += arr[i][j]; } } cout << sum << endl; return 0; } // contributed by akashish__> Java /*package whatever //do not write package name here */ import java.io.*; class GFG { public static void main(String[] args) { int n = 3; int m = 3; int arr[][] = { { 3, 2, 7 }, { 2, 6, 8 }, { 5, 1, 9 } }; int sum = 0; // Iterating over all 1-D arrays in 2-D array for (int i = 0; i < n; i++) { // Printing all elements in ith 1-D array for (int j = 0; j < m; j++) { // Printing jth element of ith row sum += arr[i][j]; } } System.out.println(sum); } } // akashish__> Python 3 n = 3 m = 3 arr = [[3, 2, 7], [2, 6, 8], [5, 1, 9]] sum = 0 # Iterating over all 1-D arrays in 2-D array for i in range(n): # Printing all elements in ith 1-D array for j in range(m): # Printing jth element of ith row sum += arr[i][j] print(sum) # This code id contributed by shivhack999>
C# using System; class MainClass { static void Main(string[] args) { int n = 3; int m = 3; int[, ] arr = { { 3, 2, 7 }, { 2, 6, 8 }, { 5, 1, 9 } }; int sum = 0; // Iterating over all 1-D arrays in 2-D array for (int i = 0; i < n; i++) { // Printing all elements in ith 1-D array for (int j = 0; j < m; j++) { // Printing jth element of ith row sum += arr[i, j]; } } Console.WriteLine(sum); } }> Javascript let n = 3; let m = 3; let arr = [[3, 2, 7], [2, 6, 8], [5, 1, 9]]; let sum = 0; // Iterating over all 1-D arrays in 2-D array for (let i = 0; i < n; i++) { // Printing all elements in ith 1-D array for (let j = 0; j < m; j++) { // Printing jth element of ith row sum += arr[i][j]; } } console.log(sum);> Lähtö
43>
Aika monimutkaisuus: O(n*m)
Ohjelma iteroi kaikkien 2D-taulukon elementtien läpi käyttämällä kahta sisäkkäistä silmukkaa. Ulompi silmukka iteroituu n kertaa ja sisempi silmukka m kertaa ulomman silmukan jokaisella iteraatiolla. Siksi ohjelman aikamonimutkaisuus on O(n*m).
Aputila: O(n*m)
Ohjelma käyttää kiinteää määrää aputilaa 2D-taulukon ja muutaman kokonaislukumuuttujan tallentamiseen. 2D-taulukon vaatima tila on nm kokonaislukua. Ohjelma käyttää myös yhtä kokonaislukumuuttujaa elementtien summan tallentamiseen. Siksi ohjelman apuavaruuden monimutkaisuus on O(nm + 1), mikä yksinkertaistuu arvoon O(n*m).
Yhteenvetona voidaan todeta, että ohjelman aikakompleksisuus on O(nm) ja apuavaruuden kompleksisuus on myös O(nm).
Joten yllä olevista esimerkeistä voimme päätellä, että suoritusaika pitenee sen mukaan, minkä tyyppisiä operaatioita teemme syötteitä käyttämällä.
Kuinka vertailla algoritmeja?
Algoritmejen vertailua varten määritellään muutama objektiivinen mitta:
- Toteutusajat: Ei hyvä mitta, koska suoritusajat ovat tietylle tietokoneelle ominaisia.
- Suoritettujen lausuntojen määrä: Ei hyvä mitta, koska lauseiden määrä vaihtelee ohjelmointikielen ja yksittäisen ohjelmoijan tyylin mukaan.
- Ihanteellinen ratkaisu: Oletetaan, että ilmaisemme tietyn algoritmin käyntiajan syötteen koon n funktiona (eli f(n)) ja vertaamme näitä eri ajoaikoja vastaavia toimintoja. Tällainen vertailu on riippumaton koneajasta, ohjelmointityylistä jne.
Siksi algoritmien vertailuun voidaan käyttää ihanteellista ratkaisua.
Aiheeseen liittyvät artikkelit:
pythonin koko
- Aika monimutkaisuus ja tilan monimutkaisuus
- Algoritmien analyysi | Sarja 1 (asymptoottinen analyysi)
- Algoritmien analyysi | Sarja 2 (pahin, keskimääräinen ja paras tapaus)
- Algoritmien analyysi | Sarja 3 (asymptoottiset merkinnät)
- Algoritmien analyysi | Sarja 4 (silmukoiden analyysi)
- Algoritmin analyysi | Sarja 5 (Amortisoidun analyysin esittely)
- Sekalaiset ajan monimutkaisuuden ongelmat
- Harjoittele kysymyksiä ajan monimutkaisuusanalyysistä
- Kilpailullisen ohjelmoinnin monimutkaisuuden tunteminen