Створення відносних складностей часу в різних мовах програмування

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

Для вимірювання їх ефективності були створені деякі параметри. Сьогодні існують два основні параметри, відомі як складність часу та складність простору, для оцінки точності коду для конкретного завдання.

Ця стаття присвячена параметру СКЛАДНІСТЬ ЧАСУ. Асимптоптичні позначення — це ті, що ми використовуємо для отримання складності часу коду. Як випливає з назви, це просто позначення або спосіб виміряти код за часом. Вони не дають нам реального уявлення про те, скільки часу код потребує для виконання.

Є три основних асимптоптичних позначення:

1. Позначення Big-O (O-нотація)
2. Позначення Omega (Ω-нотація)
3. Позначення Theta (Θ-нотація)

Основні моменти:

• Асимптоптичні позначення — це математичні інструменти, які використовуються для аналізу ефективності алгоритмів, розуміючи, як їхня ефективність змінюється в залежності від розміру введених даних.
• Ці позначення надають стиснутий спосіб вираження поведінки часу або складності простору алгоритму, коли розмір введених даних наближається до нескінченності.
• Замість того, щоб порівнювати алгоритми безпосередньо, асимптоптичний аналіз фокусується на розумінні відносних темпів зростання складностей алгоритмів.
• Це дозволяє порівнювати ефективність алгоритмів, абстрагуючи машинні специфічні константи та деталі реалізації, замість цього зосереджуючись на основних тенденціях.
• Асимптоптичний аналіз дозволяє порівнювати складність простору і часу алгоритмів, досліджуючи їхні характеристики ефективності, коли розмір введених даних змінюється.
• Використовуючи асимптоптичні позначення, такі як Big O, Big Omega і Big Theta, ми можемо класифікувати алгоритми за їхньою найгіршою, найкращою або середньою складністю часу або простору, що дає корисну інформацію про їхню ефективність.

Ця стаття фокусується на Big O, O() позначеннях. Ось деякі основні позначення Big O:

1. O(log(n))
2. O(n)
3. O(nlog(n))
4. O(n²)
5. O(a^n)
   6.
   Створення відносних складностей часу в різних мовах програмування

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

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

Ця стаття присвячена параметру СКЛАДНІСТЬ ЧАСУ. Асимптоптичні позначення — це ті, що ми використовуємо для визначення складності часу коду. Як випливає з назви, це просто позначення або спосіб виміряти код за часом. Вони не дають нам реального уявлення про те, скільки часу код потребує для виконання.

Існують три основних асимптоптичних позначення:

1. Позначення Big-O (O-нотація)
2. Позначення Omega (Ω-нотація)
3. Позначення Theta (Θ-нотація)

Основні моменти:

• Асимптоптичні позначення — це математичні інструменти, які використовуються для аналізу ефективності алгоритмів, розуміючи, як змінюється їхня ефективність із ростом розміру введених даних.
• Ці позначення надають стиснутий спосіб вираження поведінки часу або складності простору алгоритму, коли розмір введених даних наближається до нескінченності.
• Замість прямого порівняння алгоритмів, асимптоптичний аналіз фокусується на розумінні відносних темпів зростання складності алгоритмів.
• Це дозволяє порівнювати ефективність алгоритмів, абстрагуючи машинні специфічні константи та деталі реалізації, зосереджуючись на основних тенденціях.
• Асимптоптичний аналіз дозволяє порівнювати складність простору і часу алгоритмів, досліджуючи їхні характеристики ефективності, коли розмір введених даних змінюється.
• Використовуючи асимптоптичні позначення, такі як Big O, Big Omega і Big Theta, ми можемо класифікувати алгоритми за їхньою найгіршою, найкращою або середньою складністю часу або простору, що дає корисну інформацію про їхню ефективність.

Ця стаття фокусується на Big O, O() позначеннях. Ось деякі основні позначення Big O:

1. O(log(n))
2. O(n)
3. O(nlog(n))
4. O(n²)
5. O(a^n)
6. O(n!)

Збільшення порядку цих позначень відносно часу виконання:

O(log(n)) < O(n) < O(nlog(n)) < O(n²) < O(a^n) < O(n!)

У цій статті я написав алгоритми на трьох мовах програмування для всіх цих 6 позначень Big O.

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

В кінці кожного алгоритму в кожній мові виводиться реальний час виконання.

Весь код доступний на Github

Python

## СКЛАДНОСТІ ЧАСУ  

import time  
import random  

print("НАЧАТОК ДЛЯ PYTHON ................")  

## O(n)  

start_o_of_n_time=time.time()  
count=10000000  
numbers_=[]  
for v in range(1,count+1):  
 numbers_.append(v)  

end_o_of_n_time=time.time()  
n_time=end_o_of_n_time-start_o_of_n_time  
print(f"Час, витрачений на підрахунок {count} : ",n_time)  


## O(n^2)  

count =10000  
numbers_on2 = [v for v in range(1,count+1)]  
start_o_of_n_squared_time=time.time()  
for i in range(len(numbers_on2)):  
 for j in range(len(numbers_on2)):  
 multiply=numbers_on2[i]*numbers_on2[j]  
end_o_of_n_squared_time=time.time()  
n2_time=end_o_of_n_squared_time-start_o_of_n_squared_time  

print(f"Час, витрачений на операцію n_squared з {count} : ",n2_time)  


## O(n.log(n))  

count_nlogn =10000000  
numbers_nlogn = [v for v in range(1,count_nlogn+1)]  

start_o_of_n_logn_time=time.time()  
numbers_nlogn.sort()  

result = {}  
current_count = 1  
n = len(numbers_nlogn)  

# Підрахунок кількості кожного елемента  
for i in range(1, n):  
 if numbers_nlogn[i] == numbers_nlogn[i - 1]:  
 current_count += 1  
 else:  
 result[numbers_nlogn[i - 1]] = current_count  
 current_count = 1  
end_o_of_n_logn_time=time.time()  

nlogn_time=end_o_of_n_logn_time-start_o_of_n_logn_time  

print(f"Час, витрачений на операцію n_logn з {count_nlogn} : ",nlogn_time)  


## O(log(n))  


count_logn= 10000000  
numbers_logn = sorted([random.randint(1, count_logn) for _ in range(count_logn)])   

search_for = numbers_logn[random.randint(0, count_logn-1)]  


start_time_logn = time.time()  

low, high = 0, len(numbers_logn) - 1  
found = False  

while low <= high:  
 mid = (low + high) // 2  
 if numbers_logn[mid] == search_for:  
 found = True  
 break  
 elif numbers_logn[mid] < search_for:  
 low = mid + 1  
 else:  
 high = mid - 1  

# Кінцевий час  
end_time_logn = time.time()  

# Обчислення і виведення часу  
logn_time = end_time_logn - start_time_logn  

print(f"Час, витрачений на операцію logn з {count_logn} : ",logn_time)  



## O(a^n)  


def power(a, n):  
 result = 1  
 for _ in range(n):  
 result *= a  
 return result  

a = 2  
n = 100000  

start_time_o_a_power_n = time.time()  
result = power(a, n)  
end_time_o_a_power_n = time.time()  
a_raise_n_time=end_time_o_a_power_n-start_time_o_a_power_n  

print(f"Час, витрачений на операцію a^n при a = {a} та n = {n} : ",a_raise_n_time)  


### O(n!)  


n_fact = 20   
start_n_fact = time.time()  
result = 1  
for i in range(1, n + 1):  
 result *= i  
end_n_fact= time.time()  
time__n_fact=end_n_fact-start_n_fact  

print(f"Час, витрачений на операцію n-факториал з n = {n_fact} : ",time__n_fact)  


print("КІНЕЦЬ ДЛЯ PYTHON ................")

JAVA

import java.util.*;  

public class TimeComplexities {  

 public static void main(String[] args) {  
 System.out.println("НАЧАТОК ДЛЯ JAVA ................");  
 oOfN();  
 oOfNSquared();  
 oOfNLogN();  
 oOfLogN();  
 aToN();  
 nFactorial();  
 System.out.println("КІНЕЦЬ ДЛЯ JAVA ................");  
 }  

 public static void oOfN() {  
 long start = System.nanoTime();  
 int count = (int) 10000000;  
 List numbers = new ArrayList<>();  
 for (int v = 1; v <= count; v++) {  
 numbers.add(v);  
 }  
 long end = System.nanoTime();  

O(n!)

Збільшення порядку цих позначень відносно часу виконання:

## O(log(n)) < O(n) < O(nlog(n)) < O(n²) < O(a^n) < O(n!)

У цій статті я написав алгоритми на трьох мовах програмування для всіх цих 6 позначень Big O.

## Метою цієї статті не є доведення наведеного факту, а створення відносності між різними мовами програмування для цих 6 параметрів.

В кінці кожного алгоритму в кожній мові виводиться реальний час виконання.

Весь код доступний на [**Github**](https://github.com/Mritunjay1121/time_complexity_comparison)

# **Python**

СКЛАДНОСТІ ЧАСУ

import time
import random

print("НАЧАТОК ДЛЯ PYTHON ................")

O(n)

startoofntime=time.time()
count=10000000
numbers=[]
for v in range(1,count+1):
numbers.append(v)

endoofntime=time.time()
ntime=endoofntime-startoofntime
print(f"Час, витрачений на підрахунок {count} : ",ntime)

O(n^2)

count =10000
numberson2 = [v for v in range(1,count+1)]
startoofnsquaredtime=time.time()
for i in range(len(numberson2)):
for j in range(len(numberson2)):
multiply=numberson2[i]*numberson2[j]
endoofnsquaredtime=time.time()
n2time=endoofnsquaredtime-startoofnsquaredtime

print(f"Час, витрачений на операцію nsquared з {count} : ",n2time)

O(n.log(n))

countnlogn =10000000
numbersnlogn = [v for v in range(1,count_nlogn+1)]

startoofnlogntime=time.time()
numbersnlogn.sort()

result = {}
currentcount = 1
n = len(numbersnlogn)

Підрахунок кількості кожного елемента

for i in range(1, n):
if numbersnlogn[i] == numbersnlogn[i - 1]:
currentcount += 1
else:
result[numbersnlogn[i - 1]] = currentcount
currentcount = 1
endoofnlogn_time=time.time()

nlogntime=endoofnlogntime-startoofnlogn_time

print(f"Час, витрачений на операцію nlogn з {countnlogn} : ",nlogn_time)

O(log(n))

countlogn= 10000000
numberslogn = sorted([random.randint(1, countlogn) for _ in range(countlogn)])

searchfor = numberslogn[random.randint(0, count_logn-1)]

starttimelogn = time.time()

low, high = 0, len(numbers_logn) - 1
found = False

while low <= high:
mid = (low + high) // 2
if numberslogn[mid] == searchfor:
found = True
break
elif numberslogn[mid] < searchfor:
low = mid + 1
else:
high = mid - 1

Кінцевий час

endtimelogn = time.time()

Обчислення і виведення часу

logntime = endtimelogn - starttime_logn

print(f"Час, витрачений на операцію logn з {countlogn} : ",logntime)

O(a^n)

def power(a, n):
result = 1
for _ in range(n):
result *= a
return result

a = 2
n = 100000

starttimeoapowern = time.time()
result = power(a, n)
endtimeoapowern = time.time()
araisentime=endtimeoapowern-starttimeoapower_n

print(f"Час, витрачений на операцію a^n при a = {a} та n = {n} : ",araisen_time)

O(n!)

nfact = 20
startnfact = time.time()
result = 1
for i in range(1, n + 1):
result *= i
endnfact= time.time()
timenfact=endnfact-startnfact

print(f"Час, витрачений на операцію n-факториал з n = {nfact} : ",timenfact)

print("КІНЕЦЬ ДЛЯ PYTHON ................")
```

JAVA

import java.util.*;  

public class TimeComplexities {  

 public static void main(String[] args) {  
 System.out.println("НАЧАТОК ДЛЯ JAVA ................");  
 oOfN();  
 oOfNSquared();  
 oOfNLogN();  
 oOfLogN();  
 aToN();  
 nFactorial();  
 System.out.println("КІНЕЦЬ ДЛЯ JAVA ................");  
 }  

 public static void oOfN() {  
 long start = System.nanoTime();  
 int count = (int) 10000000;  
 List numbers = new ArrayList<>();  
 for (int v = 1; v <= count; v++) {  
 numbers.add(v);  
 }  
 long end = System.nanoTime();  
 System.out.println("Час, витрачений на підрахунок " + count + " : " + (end - start) / 1e9 + " секунд");  
 }  

 public static void oOfNSquared() {  
 int count = 10000;  
 List numbers = new ArrayList<>();  
 for (int v = 1; v <= count; v++) {  
 numbers.add(v);  
 }  
 long start = System.nanoTime();  
 for (int i = 0; i < count; i++) {  
 for (int j = 0; j < count; j++) {  
 int multiply = numbers.get(i) * numbers.get(j);  
 }  
 }  
 long end = System.nanoTime();  
 System.out.println("Час, витрачений на операцію n_squared з " + count + " : " + (end - start) / 1e9 + " секунд");  
 }  

 public static void oOfNLogN() {  
 int count_nlogn = (int) 10000000;  
 List numbers_nlogn = new ArrayList<>();  
 for (int v = 1; v <= count_nlogn; v++) {  
 numbers_nlogn.add(v);  
 }  
 long start = System.nanoTime();  
 Collections.sort(numbers_nlogn);  

 // Підрахунок кількості  
 Map result = new HashMap<>();  
 int current_count = 1;  
 for (int i = 1; i < count_nlogn; i++) {  
 if (numbers_nlogn.get(i).equals(numbers_nlogn.get(i - 1))) {  
 current_count++;  
 } else {  
 result.put(numbers_nlogn.get(i - 1), current_count);  
 current_count = 1;  
 }  
 }  

 long end = System.nanoTime();  
 System.out.println("Час, витрачений на операцію n_logn з " + count_nlogn + " : " + (end - start) / 1e9 + " секунд");  
 }  

 public static void oOfLogN() {  
 int count_logn = (int) 10000000;  
 List numbers_logn = new ArrayList<>();  
 Random rand = new Random();  
 for (int i = 0; i < count_logn; i++) {  
 numbers_logn.add(rand.nextInt(10000000) + 1);  
 }  
 Collections.sort(numbers_logn);  
 int search_for = numbers_logn.get(rand.nextInt(count_logn));  

 long start = System.nanoTime();  
 int low = 0, high = count_logn - 1;  
 boolean found = false;  
 while (low <= high) {  
 int mid = low + (high - low) / 2;  
 if (numbers_logn.get(mid) == search_for) {  
 found = true;  
 break;  
 }  
 if (numbers_logn.get(mid) < search_for) {  
 low = mid + 1;  
 } else {  
 high = mid - 1;  
 }  
 }  
 long end = System.nanoTime();  
 System.out.println("Час, витрачений на операцію logn з " + count_logn + " : " + (end - start) / 1e9 + " секунд");  
 }  

 public static void aToN() {  
 long a = 2;   
 long n = 100000;   

 long start = System.nanoTime();  

 long result = 1;  
 for (long i = 0; i < n; i++) {  
 result *= a;  
 }  

 long end = System.nanoTime();  

 System.out.println("Час, витрачений на операцію a^n при a = " + a + " та n= " + n + " : " + (end - start) / 1e9 + " секунд");  
 }  

 public static void nFactorial() {  
 int n = 20;   
 long start = System.nanoTime();  
 long result = 1;  
 for (int i = 1; i <= n; i++) {  
 result *= i;  
 }  
 long end = System.nanoTime();  
 System.out.println("Час, витрачений на операцію n-факториал з n= " + n + " : " + (end - start) / 1e9 + " секунд");  

 }  


}

CPP

#include   
#include   
#include   
#include   
#include   

using namespace std;  
using namespace std::chrono;  

void o_of_n() {  
 auto start = high_resolution_clock::now();  
 int count = 1e8;  
 vector numbers;  
 for (int v = 1; v <= count; ++v) {  
 numbers.push_back(v);  
 }  
 auto stop = high_resolution_clock::now();  
 auto duration = duration_cast(stop - start);  
 cout << "Час, витрачений на підрахунок " << count << " : " << duration.count() / 1e6 << " секунд" << endl;  
}  

void o_of_n_squared() {  
 int count = 10000;  
 vector numbers(count);  
 for (int v = 1; v <= count; ++v) {  
 numbers[v - 1] = v;  
 }  
 auto start = high_resolution_clock::now();  
 for (int i = 0; i < count; ++i) {  
 for (int j = 0; j < count; ++j) {  
 int multiply = numbers[i] * numbers[j];  
 }  
 }  
 auto stop = high_resolution_clock::now();  
 auto duration = duration_cast(stop - start);  

cout << "Час, витрачений на операцію n_squared з " << count << " : " << duration.count() / 1e6 << " секунд" << endl;  
}  

void o_of_n_logn() {  
 int count_nlogn = 1e8;  
 vector numbers_nlogn(count_nlogn);  
 for (int v = 1; v <= count_nlogn; ++v) {  
 numbers_nlogn[v - 1] = v;  
 }  
 auto start = high_resolution_clock::now();  
 sort(numbers_nlogn.begin(), numbers_nlogn.end());  

 // Підрахунок кількості  
 int current_count = 1;  
 for (int i = 1; i < count_nlogn; ++i) {  
 if (numbers_nlogn[i] == numbers_nlogn[i - 1]) {  
 current_count++;  
 } else {  
 current_count = 1;  
 }  
 }  

 auto stop = high_resolution_clock::now();  
 auto duration = duration_cast(stop - start);  
 cout << "Час, витрачений на операцію n_logn з " << count_nlogn << " : " << duration.count() / 1e6 << " секунд" << endl;  
}  

void o_of_logn() {  
 int count_logn = 1e7;  
 vector numbers_logn(count_logn);  
 random_device rd;  
 mt19937 gen(rd());  
 uniform_int_distribution<> dis(1, 1e7);  

 for (int i = 0; i < count_logn; ++i) {  
 numbers_logn[i] = dis(gen);  
 }  
 sort(numbers_logn.begin(), numbers_logn.end());  
 int search_for = numbers_logn[dis(gen) % count_logn];  

 auto start = high_resolution_clock::now();  
 int low = 0, high = count_logn - 1;  
 bool found = false;  
 while (low <= high) {  
 int mid = low + (high - low) / 2;  
 if (numbers_logn[mid] == search_for) {  
 found = true;  
 break;  
 }  
 if (numbers_logn[mid] < search_for) {  
 low = mid + 1;  
 } else {  
 high = mid - 1;  
 }  
 }  
 auto stop = high_resolution_clock::now();  
 auto duration = duration_cast(stop - start);  
 cout << "Час, витрачений на операцію logn з " << count_logn << " : " << duration.count() / 1e6 << " секунд" << endl;  
}  

long long power(long long a, unsigned long long n) {  
 long long result = 1;  
 for (unsigned long long i = 0; i < n; ++i) {  
 result *= a;  
 }  
 return result;  
}  

void a_to_n() {  
 long long a = 2; // Основа  
 unsigned long long n = 100000; // Показник  

 auto start = high_resolution_clock::now();  
 long long result = power(a, n);  
 auto stop = high_resolution_clock::now();  

 auto duration = duration_cast(stop - start);  
 cout << "Час, витрачений на операцію a^n при a = " << a << " та n = "<< " n: " << duration.count() / 1e6 << " секунд" << endl;  

}  
void n_factorial() {  
 int n = 20; // Приклад n, залиште невеликим, щоб уникнути переповнення  
 auto start = high_resolution_clock::now();  
 long long result = 1;  
 for (int i = 1; i <= n; ++i) {  
 result *= i;  
 }  
 auto stop = high_resolution_clock::now();  

 auto duration = duration_cast(stop - start);  
 cout << "Час, витрачений на операцію n-факториал з n= " << n << " : " << duration.count() / 1e6 << " секунд" << endl;  



}  


int main() {  
 cout << "НАЧАТОК ДЛЯ CPP ................" << endl;  
 o_of_n();  
 o_of_n_squared();  
 o_of_n_logn();  
 o_of_logn();  
 a_to_n();  
 n_factorial();  
 cout << "КІНЕЦЬ ДЛЯ CPP ................" << endl;  
 return 0;  
}

РЕЗУЛЬТАТИ

З результатів вище можна зробити висновок, що

JAVA є найшвидшою.

Тепер давайте створимо відносність для основних складностей часу.

Відносність на основі перетворення часу:

Для O(n²):

• Java: 0.61 секунди
• C++: 1.67 секунди
• Python: 71.92 секунди

Співвідношення:

• C++ до Java: Час C++ на час Java = 1.67 / 0.61 ≈ 2.74
  → 1 секунда в Java означає 2.74×1 секунду в C++.
• Python до Java: 71.92 / 0.61 ≈ 117.9
  → 1 секунда в Java означає 117.9×1 секунду в Python.

Результат:

• 1 секунда в Java = 2.74 секунди в C++

• 1 секунда в Java = 118 секунд в Python

  Для O(n!):

• Java: 3.3e-6 секунд

• C++: 1e-6 секунд

• Python: 7.91 секунд

Співвідношення:

• C++ до Java: 1e−6 / 3.3e−6 ≈ 0.3
  → 1 секунда в Java означає 0.3×1 секунду в C++.
• Python до Java: 7.91 / 3.3e−6 ≈ 2.4×10^6
  → 1 секунда в Java означає 2.4×10^6 секунд у Python.

Результат:

• 1 секунда в Java = 0.3 секунди в C++
• 1 секунда в Java = 2,400,000 секунд у Python

Для O(a^n):

• Java: 0.0061 секунд
• C++: 0.00069 секунд
• Python: 1.248 секунд

Співвідношення:

• C++ до Java: 0.00069 / 0.0061 ≈ 0.11
  → 1 секунда в Java означає 0.11×1 секунду в C++.
• Python до Java: 1.248 / 0.0061 ≈ 204.52
  → 1 секунда в Java означає 204.52×1 секунду в Python.

Результат:

• 1 секунда в Java = 0.11 секунди в C++
• 1 секунда в Java = 205 секунд у Python

Таким чином, ми можемо обчислювати відносність і використовувати її далі.

Примітка: Це лише спосіб спростити позначення та обчислити відносність.
Оскільки числа відносності можуть відрізнятися залежно від конфігурації вашої системи та інших паралельно виконуваних процесів, не слід вважати їх абсолютною істинною.

Дякую за прочитання. Плескайте, якщо ви дізналися щось нове. Скоро повернуся з новими ідеями та реалізаціями.

Перекладено з: Relative Real Time Complexities