/
Konst_And
/
Labs_cpp
Обзор
Документация
Войти
/
Konst_And
/
Labs_cpp
Код
Запросы
0
Задачи
Вики
Пакеты
0
Релизы
0
CI/CD
Аналитика
Безопасность
master
lab01/task1_python.py
132 строки
6 KB
And Konst
move py files
05 мар 2026, 15:15
05 мар 2026, 15:15
2995f69
Код
Авторство
О чём код?
# Задание 1: поиск import numpy as np import matplotlib.pyplot as plt from scipy import optimize # данные sizes_1 = [100, 200, 400, 800, 1600, 3200, 6400, 12800, 25600, 51200, 102400, 204800, 409600, 819200, 1638400] lin_avg = [0.175, 0.313, 0.627, 1.213, 2.418, 4.823, 9.697, 19.256, 38.634, 80.205, 156.362, 306.469, 602.687, 1188.92, 2369.9] lin_worst = [0.206, 0.428, 0.817, 1.604, 3.188, 6.378, 12.741, 25.682, 51.349, 102.687, 204.288, 411.528, 823.074, 1642.1, 3282.9] bin_avg = [0.05655, 0.0637, 0.07268, 0.08081, 0.09243, 0.09915, 0.10548, 0.1107, 0.11707, 0.1207, 0.13142, 0.14478, 0.15366, 0.16852, 0.24467] bin_worst = [0.02518, 0.03438, 0.03333, 0.03728, 0.04069, 0.05636, 0.05062, 0.05652, 0.05645, 0.06061, 0.06419, 0.06679, 0.07217, 0.07582, 0.08099] # функции аппроксимации def linear(x, a, b): return a * x + b def logarithmic(x, a, b): return a * np.log(x) + b # Задание 1: линейный поиск for data, name, color in [(lin_avg, 'средний', 'blue'), (lin_worst, 'худший', 'red')]: plt.figure(figsize=(12, 5)) plt.suptitle(f'Линейный поиск – {name} случай', fontsize=14, y=0.98) # Линейная аппроксимация t(N) plt.subplot(1, 2, 1) plt.plot(sizes_1, data, 'o-', color=color, linewidth=2, markersize=6, label='Данные') popt, _ = optimize.curve_fit(linear, sizes_1, data) x_fit = np.linspace(min(sizes_1), max(sizes_1), 100) plt.plot(x_fit, linear(x_fit, *popt), '--', color='black', linewidth=2, label=fr'$T = {popt[0]:.4f}\cdot N + {popt[1]:.2f}$') plt.xlabel('Размер массива N') plt.ylabel('Время (мкс)') plt.title('t(N) – линейная аппроксимация') plt.grid(True, alpha=0.3) plt.legend() plt.subplot(1, 2, 2) plt.plot(sizes_1, data, 'o-', color=color, linewidth=2, markersize=6, label='Данные') plt.xlabel('Размер массива N') plt.ylabel('Время (мкс)') plt.title('t(N)') plt.grid(True, alpha=0.3) plt.legend() plt.tight_layout(rect=[0, 0, 1, 0.95]) #plt.savefig(f'task1_lin_{name}.png', dpi=300) plt.show() # Задание 1: бинарный поиск for data, name, color in [(bin_avg, 'средний', 'green'), (bin_worst, 'худший', 'orange')]: plt.figure(figsize=(12, 5)) plt.suptitle(f'Бинарный поиск – {name} случай', fontsize=14, y=0.98) # Логарифмическая аппроксимация t(N) plt.subplot(1, 2, 1) plt.plot(sizes_1, data, 'o-', color=color, linewidth=2, markersize=6, label='Данные') popt_log, _ = optimize.curve_fit(logarithmic, sizes_1, data) x_fit = np.linspace(min(sizes_1), max(sizes_1), 100) plt.plot(x_fit, logarithmic(x_fit, *popt_log), '--', color='black', linewidth=2, label=fr'$T = {popt_log[0]:.2f}\cdot \ln(N) + {popt_log[1]:.2f}$') plt.xlabel('Размер массива N') plt.ylabel('Время (мкс)') plt.title('t(N) – логарифмическая аппроксимация') plt.grid(True, alpha=0.3) plt.legend() # Линеаризация в координатах t(ln(N)) plt.subplot(1, 2, 2) log_sizes = np.log(sizes_1) plt.plot(log_sizes, data, 'o-', color=color, linewidth=2, markersize=6, label='Данные') popt_lin, _ = optimize.curve_fit(linear, log_sizes, data) x_log_fit = np.linspace(min(log_sizes), max(log_sizes), 100) plt.plot(x_log_fit, linear(x_log_fit, *popt_lin), '--', color='black', linewidth=2, label=fr'$T = {popt_lin[0]:.2f}\cdot \ln(N) + {popt_lin[1]:.2f}$') plt.xlabel('ln(N)') plt.ylabel('Время (мкс)') plt.title('t(ln(N)) – линеаризация') plt.grid(True, alpha=0.3) plt.legend() plt.tight_layout(rect=[0, 0, 1, 0.95]) #plt.savefig(f'task1_bin_{name}.png', dpi=300) plt.show() # Совместные графики для сравнения линейного и бинарного поиска # Худшие случаи plt.figure(figsize=(14, 6)) plt.subplot(1, 2, 1) plt.loglog(sizes_1, lin_worst, 'ro-', linewidth=2, markersize=8, label='Линейный поиск (худший)') plt.loglog(sizes_1, bin_worst, 'bo-', linewidth=2, markersize=8, label='Бинарный поиск (худший)') plt.xlabel('Размер массива N', fontsize=12) plt.ylabel('Время (мкс)', fontsize=12) plt.title('Сравнение алгоритмов поиска (худший случай)', fontsize=14) plt.grid(True, alpha=0.3, which='both') plt.legend(fontsize=12) # Средние случаи plt.subplot(1, 2, 2) plt.loglog(sizes_1, lin_avg, 'ro-', linewidth=2, markersize=8, label='Линейный поиск (средний)') plt.loglog(sizes_1, bin_avg, 'go-', linewidth=2, markersize=8, label='Бинарный поиск (средний)') plt.xlabel('Размер массива N', fontsize=12) plt.ylabel('Время (мкс)', fontsize=12) plt.title('Сравнение алгоритмов поиска (средний случай)', fontsize=14) plt.grid(True, alpha=0.3, which='both') plt.legend(fontsize=12) plt.tight_layout() #plt.savefig('comparison_loglog.png', dpi=300) plt.show() # Сравнение всех случаев plt.figure(figsize=(12, 8)) plt.loglog(sizes_1, lin_worst, 'r-o', linewidth=2, markersize=8, label='Линейный (худший)', alpha=0.8) plt.loglog(sizes_1, lin_avg, 'r-s', linewidth=2, markersize=8, label='Линейный (средний)', alpha=0.6) plt.loglog(sizes_1, bin_worst, 'b-o', linewidth=2, markersize=8, label='Бинарный (худший)', alpha=0.8) plt.loglog(sizes_1, bin_avg, 'g-o', linewidth=2, markersize=8, label='Бинарный (средний)', alpha=0.8) plt.xlabel('Размер массива N', fontsize=14) plt.ylabel('Время (мкс)', fontsize=14) plt.title('Сравнение всех случаев линейного и бинарного поиска', fontsize=16) plt.grid(True, alpha=0.3, which='both') plt.legend(fontsize=12, loc='upper left') plt.tight_layout() #plt.savefig('efficiency_comparison.png', dpi=300) plt.show()