logo

TechCodeview

Laiko sudėtingumo supratimas paprastais pavyzdžiais

Daugelis studentų susipainioja suprasdami laiko sudėtingumo sąvoką, tačiau šiame straipsnyje mes tai paaiškinsime labai paprastu pavyzdžiu.

K. Įsivaizduokite klasę, kurioje yra 100 mokinių, kurioje jūs davėte rašiklį vienam asmeniui. Jūs turite rasti tą rašiklį nežinodami, kam jį davei.



Štai keletas būdų, kaip rasti rašiklį ir kokia yra O tvarka.

  • O (n 2 ): Einate ir paklausite pirmojo asmens klasėje, ar jis turi rašiklį. Taip pat paklauskite šio asmens apie kitus 99 žmones klasėje, ar jie turi tą rašiklį ir pan.
    Tai mes vadiname O (n2).
  • O(n): Eiti ir klausti kiekvieno mokinio atskirai yra O(N).
  • O(log n): Dabar aš padalijau klasę į dvi grupes, tada klausiu: Ar ji yra kairėje, ar dešinėje klasės pusėje? Tada paimu tą grupę ir padalinu į dvi dalis ir vėl klausiu ir t.t. Kartokite procesą, kol liks vienas mokinys, turintis rašiklį. Štai ką jūs turite omenyje sakydami O(log n).

Man gali prireikti:

  • The O (n 2 ) ieško, jei tik vienas mokinys žino, ant kurio mokinio paslėptas rašiklis .
  • The O(n) jeigu vienas mokinys turėjo rašiklį ir tik jie jį žinojo .
  • The O(log n) ieškoti jei visi mokiniai žinojo , bet man pasakytų tik tada, jei atspėčiau teisingą pusę.

Aukščiau O -> vadinamas Didelis - Oh kuris yra asimptotinis žymėjimas. Yra ir kitų asimptotinės žymos Kaip teta ir Omega .



PASTABA: Mus domina augimo tempas laikui bėgant, atsižvelgiant į programos vykdymo metu gautus duomenis.

Ar algoritmo / kodo laiko sudėtingumas yra toks pat kaip kodo veikimo / vykdymo laikas?

Algoritmo / kodo laiko sudėtingumas yra ne lygus faktiniam laikui, kurio reikia tam tikram kodui įvykdyti, bet sakinio įvykdymo skaičiui. Tai galime įrodyti naudodami laiko komanda .

Pavyzdžiui: Parašykite kodą C/C++ arba bet kuria kita kalba, kad surastumėte didžiausią skaičių tarp N skaičių, kur N svyruoja nuo 10, 100, 1000 ir 10 000. Jei naudojate Linux operacinę sistemą (Fedora arba Ubuntu), naudokite toliau pateiktas komandas:



gamyklos metodo projektavimo modelis

Norėdami sudaryti programą: gcc programa.c – o programa
Norėdami paleisti programą: laikas ./programa

Sulauksite netikėtų rezultatų, t. y.:

  • Jei N = 10: galite gauti 0,5 ms laiko,
  • Jei N = 10 000: galite gauti 0,2 ms laiko.
  • Be to, skirtingose ​​mašinose gausite skirtingą laiką. Net jei to paties kodo tame pačiame kompiuteryje negausite tų pačių laiko, to priežastis yra dabartinė tinklo apkrova.

Taigi, galime pasakyti, kad faktinis laikas, reikalingas kodui vykdyti, priklauso nuo mašinos (nesvarbu, ar naudojate Pentium 1, ar Pentium 5), taip pat atsižvelgiama į tinklo apkrovą, jei jūsų įrenginys yra LAN / WAN.

Ką reiškia algoritmo laiko sudėtingumas?

Dabar kyla klausimas, jei laiko sudėtingumas nėra tikrasis laikas, reikalingas kodui vykdyti, kas tai yra?

Atsakymas yra:

Užuot matę faktinį laiką, reikalingą kiekvienam kode esančiam teiginiui vykdyti, Laiko sudėtingumas įvertina, kiek kartų kiekvienas teiginys įvykdomas.

1 pavyzdys: Apsvarstykite žemiau pateiktą paprastą kodą spausdinti 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.>
Python3 
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.>
Išvestis 
Hello World>

Laiko sudėtingumas: Aukščiau pateiktame kode Hello World ekrane atspausdinamas tik vieną kartą.
Taigi, laiko sudėtingumas yra konstanta: O(1) y., kiekvieną kartą, kai reikia pastovaus laiko, kad būtų įvykdytas kodas, nesvarbu, kurią operacinę sistemą ar įrenginio konfigūracijas naudojate.
Pagalbinė erdvė : O(1)

2 pavyzdys:

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>
Python3 
# 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 !!!');  }>
Išvestis 
Hello World !!! Hello World !!! Hello World !!! Hello World !!! Hello World !!! Hello World !!! Hello World !!! Hello World !!!>

Laiko sudėtingumas: Aukščiau pateiktame kode Hello World!!! yra tik spausdinama n kartų ekrane, nes n reikšmė gali keistis.
Taigi, laiko sudėtingumas yra tiesinis: O(n) y., kiekvieną kartą, norint įvykdyti kodą, reikia linijinio laiko.
Pagalbinė erdvė: O(1)

3 pavyzdys:

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>
Python3 
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.>
Išvestis 
Hello World !!! Hello World !!! Hello World !!! Hello World !!!>

Laiko sudėtingumas: O(log2(n))
Pagalbinė erdvė: O(1)

4 pavyzdys:

C++ 
#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 !!!');  }  }  }>
Python3 
n = 8 i = 2 for j in range(2,n+1): if(i>= n): break print('Hello World !!!') i *= i # Šį kodą pateikė 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.>
Išvestis 
Hello World !!! Hello World !!!>

Laiko sudėtingumas: O(log(log n))
Pagalbinė erdvė: O(1)

Kaip rasti algoritmo laiko sudėtingumą?

Dabar pažiūrėkime į kelis kitus pavyzdžius ir algoritmo sudėtingumo laiko nustatymo procesą:

kintamasis globalus javascript

Pavyzdys: Panagrinėkime mašinos modelį, kuris turi šias specifikacijas:

  • Vienas procesorius
  • 32 bitų
  • Nuoseklus vykdymas
  • 1 laiko vienetas aritmetiniams ir loginiams veiksmams
  • 1 laiko vienetas priskyrimo ir grąžinimo ataskaitoms

Q1. Raskite 2 skaičių sumą aukščiau esančiame kompiuteryje:

Bet kurio įrenginio pseudokodas, skirtas pridėti du skaičius, bus maždaug toks:

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__>
Python3 
# 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__>
Išvestis 
11>

Laiko sudėtingumas:

  • Aukščiau pateiktas kodas užtruks 2 laiko vienetus (pastovus):
    • vienas aritmetiniams veiksmams ir
    • vienas grąžinimui. (kaip nurodyta aukščiau).
  • Taigi visos sumos operacijos atlikimo išlaidos ( ) = 1 + 1 = 2
  • Laiko sudėtingumas = O(2) = O(1) , nes 2 yra pastovus

Pagalbinė erdvė: O(1)

Q2. Raskite visų sąrašo/masyvo elementų sumą

Pseudokodas tam gali būti pateiktas taip:

C++ 
#include  using namespace std; int list_Sum(int A[], int n)   // A->masyvas ir // n->elementų skaičius masyve { int suma = 0;  už (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->masyvas ir // n-> elementų skaičius masyve { suma = 0, jei i = 0 iki n-1 sum = suma + A[i] return sum }>
Java 
// Java code for the above approach import java.io.*; class GFG {  static int list_Sum(int[] A, int n)  // A->masyvas ir // n->elementų skaičius masyve { int suma = 0;  už (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.>
Python3 
# 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->masyvas ir // n->elementų skaičius masyve { int suma = 0;  už (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->masyvas ir // n->elementų skaičius masyve { tegul suma = 0;  for (tegul 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__>
Išvestis 
14>


Norėdami suprasti anksčiau pateikto kodo sudėtingumą, pažiūrėkime, kiek laiko užtruks kiekvienas teiginys:

C++ 
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);  } }>
Python3 
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);>

Taigi visos sumos operacijos atlikimo išlaidos

Suma = 1 + 2 * (n + 1) + 2 * n + 1 = 4n + 4 = C1 * n + C2 = O (n)

Todėl aukščiau nurodyto kodo sudėtingumas laike yra O(n)

Q3. Raskite visų matricos elementų sumą

Šiuo atveju sudėtingumas yra daugianario lygtis (kvadratinė lygtis kvadratinei matricai)

  • n*n => dydžio matrica Tsum = a.n 2 + b.n + c
  • Kadangi Tsum yra n eilės tvarka2, todėl Laiko sudėtingumas = O(n 2 )
C++ 
#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__>
Python3 
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);>
Išvestis 
43>

Laiko sudėtingumas: O(n*m)
Programa kartoja visus 2D masyvo elementus naudodama dvi įdėtas kilpas. Išorinis ciklas kartojasi n kartų, o vidinis ciklas – m kartų kiekvienai išorinės kilpos iteracijai. Todėl programos laiko sudėtingumas yra O(n*m).

Pagalbinė erdvė: O(n*m)
Programa naudoja fiksuotą pagalbinės erdvės kiekį 2D masyvei ir keliems sveikiesiems kintamiesiems saugoti. 2D masyvei reikalinga erdvė yra nm sveikieji skaičiai. Programa taip pat naudoja vieną sveikąjį kintamąjį elementų sumai saugoti. Todėl programos pagalbinės erdvės sudėtingumas yra O(nm + 1), o tai supaprastėja iki O(n*m).

Apibendrinant galima pasakyti, kad programos laiko sudėtingumas yra O (nm), o pagalbinės erdvės sudėtingumas taip pat yra O (nm).

Taigi iš aukščiau pateiktų pavyzdžių galime daryti išvadą, kad vykdymo laikas ilgėja atsižvelgiant į operacijų tipą, kurį atliekame naudodami įvestis.

Kaip palyginti algoritmus?

Norėdami palyginti algoritmus, apibrėžkime keletą objektyvių priemonių:

  • Vykdymo laikai: Netinkama priemonė, nes vykdymo laikas priklauso nuo konkretaus kompiuterio.
  • Atliktų pareiškimų skaičius: Tai nėra gera priemonė, nes teiginių skaičius skiriasi priklausomai nuo programavimo kalbos ir individualaus programuotojo stiliaus.
  • Idealus sprendimas: Tarkime, kad tam tikro algoritmo veikimo laiką išreiškiame kaip įvesties dydžio n funkciją (t. y. f(n)) ir palyginame šias skirtingas funkcijas, atitinkančias veikimo laiką. Toks palyginimas nepriklauso nuo mašinos laiko, programavimo stiliaus ir kt.
    Todėl algoritmams palyginti gali būti naudojamas idealus sprendimas.

Susiję straipsniai:

xd xd prasmė
  • Laiko ir erdvės sudėtingumas
  • Algoritmų analizė | 1 rinkinys (asimptotinė analizė)
  • Algoritmų analizė | 2 rinkinys (blogiausias, vidutinis ir geriausias atvejis)
  • Algoritmų analizė | 3 rinkinys (asimptotiniai žymėjimai)
  • Algoritmų analizė | 4 rinkinys (kilpų analizė)
  • Algoritmo analizė | 5 rinkinys (amortizuotos analizės įvadas)
  • Įvairios laiko sudėtingumo problemos
  • Praktiniai klausimai apie laiko sudėtingumo analizę
  • Žinodami konkursinio programavimo sudėtingumą