logo

TechCodeview

Розуміння складності часу на простих прикладах

Багато студентів плутаються, розуміючи концепцію складності часу, але в цій статті ми пояснимо це на дуже простому прикладі.

П. Уявіть собі клас із 100 студентами, де ви віддали свою ручку одній людині. Ви повинні знайти цю ручку, не знаючи, кому ви її дали.



Ось кілька способів знайти ручку та порядок O.

  • O(n 2 ): Ви йдете і запитуєте першого в класі, чи є у нього ручка. Крім того, ви запитуєте цю людину про інших 99 людей у ​​класі, чи є у них ручка тощо,
    Це те, що ми називаємо O(n2).
  • O(n): Йти і запитувати кожного студента окремо - це O(N).
  • O(log n): Тепер я поділяю клас на дві групи, а потім запитую: це ліворуч чи праворуч від класу? Потім я беру цю групу, поділяю її на дві, запитую знову і так далі. Повторюйте процес, поки у вас не залишиться один учень, у якого ваша ручка. Це те, що ви маєте на увазі під O(log n).

Мені може знадобитися зробити:

  • The O(n 2 ) шукає якщо тільки один учень знає, на якому учневі захована ручка .
  • The O(n) якщо один учень мав ручку, і тільки вони це знали .
  • The O(log n) пошук якщо знали всі учні , але скаже мені, лише якщо я вгадаю правильну сторону.

Вище О -> називається Великий – О що є асимптотичним записом. Є й інші асимптотичні позначення люблю тета і Омега .



ПРИМІТКА: Нас цікавить швидкість зростання в часі вхідних даних, зроблених під час виконання програми.

Чи збігається часова складність алгоритму/коду з часом виконання/виконання коду?

Часова складність алгоритму/коду ні дорівнює фактичному часу, необхідному для виконання певного коду, але кількості разів виконання оператора. Ми можемо довести це за допомогою команда часу .

Наприклад: Напишіть код C/C++ або будь-якою іншою мовою, щоб знайти максимальне значення між N числами, де N змінюється від 10, 100, 1000 і 10000. Для операційної системи на базі Linux (Fedora або Ubuntu) використовуйте наведені нижче команди:



стеки java

Щоб скомпілювати програму: gcc program.c – програма o
Щоб виконати програму: час ./програма

Ви отримаєте дивовижні результати, а саме:

  • Для N = 10: ви можете отримати час 0,5 мс,
  • Для N = 10 000: ви можете отримати час 0,2 мс.
  • Крім того, ви отримаєте різні таймінги на різних машинах. Навіть якщо ви не отримаєте однакові таймінги на одній машині для того самого коду, причиною цього є поточне навантаження на мережу.

Отже, можна сказати, що фактичний час, необхідний для виконання коду, залежить від машини (незалежно від того, чи використовуєте ви Pentium 1 чи Pentium 5), а також враховує навантаження на мережу, якщо ваша машина працює в LAN/WAN.

Що мається на увазі під часовою складністю алгоритму?

Тепер виникає питання, якщо часова складність не є фактичним часом, необхідним для виконання коду, тоді що це?

Відповідь:

Замість вимірювання фактичного часу, необхідного для виконання кожного оператора в коді, Часова складність враховує, скільки разів виконується кожен оператор.

приклад 1: Розгляньте наведений нижче простий код роздрукувати 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.>
Вихід 
Hello World>

Часова складність: У наведеному вище коді Hello World друкується на екрані лише один раз.
Отже, часова складність є константа: O(1) тобто щоразу, коли для виконання коду потрібен постійний проміжок часу, незалежно від того, яку операційну систему чи конфігурацію машини ви використовуєте.
Допоміжний простір : O(1)

приклад 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>
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 !!!');  }>
Вихід 
Hello World !!! Hello World !!! Hello World !!! Hello World !!! Hello World !!! Hello World !!! Hello World !!! Hello World !!!>

Часова складність: У наведеному вище коді Hello World !!! лише друкується n разів на екрані, оскільки значення n може змінюватися.
Отже, часова складність є лінійний: O(n) тобто кожен раз для виконання коду потрібен лінійний час.
Допоміжний простір: О(1)

приклад 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>
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.>
Вихід 
Hello World !!! Hello World !!! Hello World !!! Hello World !!!>

Часова складність: O(log2(n))
Допоміжний простір: О(1)

Приклад 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>
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 # Цей код створено 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.>
Вихід 
Hello World !!! Hello World !!!>

Часова складність: O(log(log n))
Допоміжний простір: О(1)

Як знайти часову складність алгоритму?

Тепер розглянемо інші приклади та процес визначення часової складності алгоритму:

приклад: Розглянемо модель машини, яка має наступні характеристики:

  • Однопроцесорний
  • 32 біт
  • Послідовне виконання
  • 1 одиниця часу на арифметичні та логічні дії
  • 1 одиниця часу для операторів призначення та повернення

Q1. Знайдіть суму 2 чисел на наведеній вище машині:

рядок java

Для будь-якої машини псевдокод для додавання двох чисел буде приблизно таким:

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__>
Вихід 
11>

Часова складність:

  • Наведений вище код займе 2 одиниці часу (константа):
    • один для арифметичних дій і
    • один для повернення. (відповідно до наведених вище угод).
  • Тому загальна вартість виконання сумарної операції ( ) = 1 + 1 = 2
  • Часова складність = O(2) = O(1) , оскільки 2 є константою

Допоміжний простір: О(1)

Q2. Знайти суму всіх елементів списку/масиву

Псевдокод для цього можна надати так:

C++ 
#include  using namespace std; int list_Sum(int A[], int n)   // A->масив і // n->кількість елементів у масиві { int sum = 0;  для (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->масив і // n->кількість елементів у масиві { сума = 0 для i = 0 до n-1 сума = сума + A[i] повертає суму }>
Java 
// Java code for the above approach import java.io.*; class GFG {  static int list_Sum(int[] A, int n)  // A->масив і // n->кількість елементів у масиві { int sum = 0;  для (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->масив і // n->кількість елементів у масиві { int sum = 0;  для (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->масив і // n->кількість елементів у масиві { let sum = 0;  для (нехай 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__>
Вихід 
14>


Щоб зрозуміти часову складність наведеного вище коду, давайте подивимося, скільки часу займе кожен оператор:

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);>

Тому загальна вартість виконання сумарної операції

Сума=1 + 2 * (n+1) + 2 * n + 1 = 4n + 4 = C1 * n + C2 = O(n)

Тому часова складність наведеного вище коду становить O(n)

Q3. Знайти суму всіх елементів матриці

Для цього рівняння складністю є поліноміальне рівняння (квадратне рівняння для квадратної матриці)

  • Матриця розміром n*n => Цум = а.н 2 + б.н + в
  • Оскільки цум в порядку н2, тому Часова складність = 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);>
Вихід 
43>

Часова складність: O(n*m)
Програма повторює всі елементи 2D-масиву за допомогою двох вкладених циклів. Зовнішній цикл повторюється n разів, а внутрішній цикл повторюється m разів для кожної ітерації зовнішнього циклу. Отже, часова складність програми становить O(n*m).

Допоміжний простір: O(n*m)
Програма використовує фіксовану кількість допоміжного простору для зберігання 2D-масиву та кількох цілочисельних змінних. Простір, необхідний для 2D-масиву, становить nm цілих чисел. Програма також використовує одну цілу змінну для зберігання суми елементів. Тому складність допоміжного простору програми становить O(nm + 1), що спрощується до O(n*m).

порівняння рядків java

Підсумовуючи, часова складність програми становить O(nm), і складність допоміжного простору також O(nm).

Отже, з наведених вище прикладів можна зробити висновок, що час виконання збільшується залежно від типу операцій, які ми виконуємо, використовуючи вхідні дані.

Як порівнювати алгоритми?

Щоб порівняти алгоритми, визначимо кілька об’єктивних показників:

  • Час виконання: Це не дуже добре, оскільки час виконання є специфічним для конкретного комп’ютера.
  • Кількість виконаних операторів: Це не дуже добре, оскільки кількість операторів залежить від мови програмування, а також від стилю окремого програміста.
  • Ідеальне рішення: Припустимо, що ми виражаємо час роботи даного алгоритму як функцію вхідного розміру n (тобто f(n)) і порівнюємо ці різні функції, що відповідають часу виконання. Таке порівняння не залежить від машинного часу, стилю програмування тощо.
    Тому для порівняння алгоритмів можна використовувати ідеальне рішення.

Пов'язані статті:

  • Часова складність і просторова складність
  • Аналіз алгоритмів | Набір 1 (Асимптотичний аналіз)
  • Аналіз алгоритмів | Набір 2 (найгірший, середній і найкращий випадки)
  • Аналіз алгоритмів | Набір 3 (Асимптотичні позначення)
  • Аналіз алгоритмів | Набір 4 (Аналіз петель)
  • Аналіз алгоритму | Набір 5 (Вступ до аналізу амортизації)
  • Різні проблеми часової складності
  • Практичні запитання з аналізу складності часу
  • Знання складності змагального програмування