logo

TechCodeview

Pochopení časové složitosti pomocí jednoduchých příkladů

Mnoho studentů je zmateno při chápání pojmu časové složitosti, ale v tomto článku si to vysvětlíme na velmi jednoduchém příkladu.

Otázka: Představte si třídu se 100 studenty, ve které jste předali své pero jedné osobě. Musíte najít to pero, aniž byste věděli, komu jste ho dali.



Zde je několik způsobů, jak najít pero a co je pořadí O.

  • Na 2 ): Jdeš a zeptáš se prvního člověka ve třídě, jestli má pero. Také se této osoby zeptáte na dalších 99 lidí ve třídě, jestli mají to pero a tak dále,
    Tomu říkáme O(n2).
  • Na): Jít a ptát se každého studenta jednotlivě je O(N).
  • O(log n): Nyní rozdělím třídu na dvě skupiny a pak se zeptám: Je to na levé nebo na pravé straně třídy? Pak vezmu tu skupinu a rozdělím ji na dvě a znovu se zeptám, a tak dále. Opakujte proces, dokud vám nezůstane jeden student, který má vaše pero. To je to, co myslíte O(log n).

Možná budu muset udělat:

  • The Na 2 ) hledá pokud pouze jeden student ví, na kterém studentovi je pero skryto .
  • The Na) -li jeden student měl pero a věděli to jen oni .
  • The O(log n) hledat pokud všichni studenti věděli , ale řekl by mi to, jen kdybych uhodl správnou stranu.

Výše Ó -> se nazývá Velký – Oh což je asymptotický zápis. Existují další asymptotické notace jako theta a Omega .



POZNÁMKA: Zajímá nás tempo růstu v čase s ohledem na vstupy přijaté během provádění programu.

Je časová složitost algoritmu/kódu stejná jako doba běhu/provedení kódu?

Časová složitost algoritmu/kódu je ne rovna skutečnému času potřebnému k provedení konkrétního kódu, ale počtu provedení příkazu. Můžeme to dokázat pomocí časový příkaz .

Například: Napište kód v C/C++ nebo jiném jazyce, abyste našli maximum mezi N čísly, kde N se pohybuje od 10, 100, 1000 a 10000. Pro operační systém založený na Linuxu (Fedora nebo Ubuntu) použijte níže uvedené příkazy:



enum tostring java

Pro kompilaci programu: gcc program.c – o program
Chcete-li spustit program: čas ./program

Dostanete překvapivé výsledky, např.

  • Pro N = 10: můžete získat čas 0,5 ms,
  • Pro N = 10 000: můžete získat čas 0,2 ms.
  • Také získáte různé časování na různých strojích. I když nezískáte stejné časování na stejném počítači pro stejný kód, důvodem je aktuální zatížení sítě.

Můžeme tedy říci, že skutečný čas potřebný k provedení kódu je závislý na stroji (ať už používáte Pentium 1 nebo Pentium 5) a také bere v úvahu zatížení sítě, pokud je váš počítač v LAN/WAN.

Co znamená časová složitost algoritmu?

Nyní vyvstává otázka, pokud časová složitost není skutečným časem potřebným k provedení kódu, co to tedy je?

Odpověď je:

Místo měření skutečného času potřebného k provedení každého příkazu v kódu, Časová složitost zohledňuje, kolikrát se každý příkaz vykoná.

Příklad 1: Zvažte níže uvedený jednoduchý kód tisk Ahoj světe

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; }>
Jáva 
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.>
Výstup 
Hello World>

Časová náročnost: Ve výše uvedeném kódu je Hello World vytištěn na obrazovce pouze jednou.
Časová složitost tedy je konstanta: O(1) tj. pokaždé, když je ke spuštění kódu potřeba konstantní množství času, bez ohledu na to, jaký operační systém nebo konfiguraci počítače používáte.
Pomocný prostor : O(1)

Příklad 2:

herec govinda
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 !!!
');  } }>
Jáva 
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 !!!');  }>
Výstup 
Hello World !!! Hello World !!! Hello World !!! Hello World !!! Hello World !!! Hello World !!! Hello World !!! Hello World !!!>

Časová náročnost: Ve výše uvedeném kódu Hello World !!! je pouze vytištěna n krát na obrazovce, protože hodnota n se může měnit.
Časová složitost tedy je lineární: O(n) tj. pokaždé je k provedení kódu zapotřebí lineární množství času.
Pomocný prostor: O(1)

Příklad 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>
Jáva 
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.>
Výstup 
Hello World !!! Hello World !!! Hello World !!! Hello World !!!>

Časová náročnost: O(log2(n))
Pomocný prostor: O(1)

Příklad 4:

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>
Jáva 
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('Ahoj světe !!!') i *= i # Tento kód přispěl 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.>
Výstup 
Hello World !!! Hello World !!!>

Časová náročnost: O(log(log n))
Pomocný prostor: O(1)

Jak zjistit časovou složitost algoritmu?

Nyní se podívejme na některé další příklady a proces hledání časové složitosti algoritmu:

Příklad: Uvažujme model stroje, který má následující specifikace:

  • Jediný procesor
  • 32 bit
  • Sekvenční provádění
  • 1 časová jednotka pro aritmetické a logické operace
  • 1 časová jednotka pro příkazy přiřazení a návrat

Q1. Najděte součet 2 čísel na výše uvedeném stroji:

Pro jakýkoli stroj bude pseudokód pro přidání dvou čísel něco takového:

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 }>
Jáva 
// 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__>
Výstup 
11>

Časová náročnost:

  • Výše uvedený kód bude trvat 2 jednotky času (konstanta):
    • jeden pro aritmetické operace a
    • jeden pro návrat. (podle výše uvedených konvencí).
  • Proto celkové náklady na provedení operace součtu ( ) = 1 + 1 = 2
  • Časová složitost = O(2) = O(1) , protože 2 je konstantní

Pomocný prostor: O(1)

Q2. Najděte součet všech prvků seznamu/pole

Pseudokód k tomu může být zadán jako:

C++ 
#include  using namespace std; int list_Sum(int A[], int n)   // A->pole a // n->počet prvků v poli { int suma = 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->pole a // n->počet prvků v poli { součet = 0 pro i = 0 až n-1 součet = součet + A[i] návratový součet }>
Jáva 
// Java code for the above approach import java.io.*; class GFG {  static int list_Sum(int[] A, int n)  // A->pole a // n->počet prvků v poli { int suma = 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.>
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->pole a // n->počet prvků v poli { int suma = 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->pole a // n->počet prvků v poli { nechť suma = 0;  for (ať 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__>
Výstup 
14>


Abychom pochopili časovou složitost výše uvedeného kódu, podívejme se, kolik času zabere každý příkaz:

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 }>
Jáva 
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);>

Proto celkové náklady na provedení operace součtu

Součet=1 + 2 * (n+1) + 2 * n + 1 = 4n + 4 = C1 * n + C2 = O(n)

Časová složitost výše uvedeného kódu tedy je Na)

Q3. Najděte součet všech prvků matice

V tomto případě je složitost polynomiální rovnice (kvadratická rovnice pro čtvercovou matici)

  • Matice velikosti n*n => Tsum = a.n 2 + b.n + c
  • Protože Tsum je v řádu n2, proto Časová složitost = 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__>
Jáva 
/*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);>
Výstup 
43>

Časová náročnost: O(n*m)
Program iteruje všechny prvky ve 2D poli pomocí dvou vnořených smyček. Vnější smyčka se iteruje nkrát a vnitřní smyčka mkrát pro každou iteraci vnější smyčky. Časová složitost programu je tedy O(n*m).

Pomocný prostor: O(n*m)
Program používá pevné množství pomocného prostoru pro uložení 2D pole a několik celočíselných proměnných. Prostor potřebný pro 2D pole je nm celá čísla. Program také používá jednu celočíselnou proměnnou k uložení součtu prvků. Pomocná prostorová složitost programu je tedy O(nm + 1), což zjednodušuje na O(n*m).

jak předělat ve photoshopu

Závěrem, časová složitost programu je O(nm) a složitost pomocného prostoru je také O(nm).

Z výše uvedených příkladů tedy můžeme usoudit, že doba provádění se zvyšuje s typem operací, které provádíme pomocí vstupů.

Jak porovnávat algoritmy?

Abychom porovnali algoritmy, definujme několik objektivních opatření:

  • Časy provedení: Není to dobré měřítko, protože doby provádění jsou specifické pro konkrétní počítač.
  • Počet provedených příkazů: Není to dobré měřítko, protože počet příkazů se liší podle programovacího jazyka a také stylu jednotlivých programátorů.
  • Ideální řešení: Předpokládejme, že vyjádříme dobu běhu daného algoritmu jako funkci vstupní velikosti n (tj. f(n)) a porovnáme tyto různé funkce odpovídající době běhu. Tento druh srovnání je nezávislý na strojovém čase, stylu programování atd.
    Proto lze použít ideální řešení pro porovnání algoritmů.

Související články:

  • Časová složitost a prostorová složitost
  • Analýza algoritmů | Sada 1 (asymptotická analýza)
  • Analýza algoritmů | Sada 2 (nejhorší, průměrné a nejlepší případy)
  • Analýza algoritmů | Sada 3 (asymptotické notace)
  • Analýza algoritmů | Sada 4 (Analýza smyček)
  • Analýza algoritmu | Sada 5 (Úvod analýzy odepsané hodnoty)
  • Různé problémy časové složitosti
  • Cvičné otázky o analýze časové složitosti
  • Znalost složitosti konkurenčního programování