Блог

Мы исследовали программное обеспечение, которое предположительно использовалось для взлома. Мы обнаружили, что время работы существенно зависит от длины ввода N, особенно когда N больше 10-15. Во время наших тестов мы исправили следующие рабочие времена.

 N = 2 - 16.38 seconds 
N = 5 - 16.38 seconds 
N = 10 - 16.44 seconds 
N = 15 - 18.39 seconds 
N = 20 - 64.22 seconds 
N = 30 - 65774.62 seconds
 

Задачи:
найдите время работы программы для следующих трех случаев —
N = 25, N = 40 и N = 50.

Я пытался выполнить полиномиальную регрессию, но прогнозы варьировались от степени 2,3, …

 # Importing the libraries 
import numpy as np 
import matplotlib.pyplot as plt 

# Importing the dataset 
X = np.array([[2],[5],[10],[15],[20],[30]])
X_predict = np.array([[25], [40], [50]])
y = np.array([[16.38],[16.38],[16.44],[18.39],[64.22],[65774.62]])
#y = np.array([[16.38/60],[16.38/60],[16.44/60],[18.39/60],[64.22/60],[65774.62/60]])


# Fitting Polynomial Regression to the dataset 
from sklearn.preprocessing import PolynomialFeatures 

poly = PolynomialFeatures(degree = 11) 
X_poly = poly.fit_transform(X) 

poly.fit(X_poly, y) 
lin2 = LinearRegression() 
lin2.fit(X_poly, y) 

# Visualising the Polynomial Regression results 
plt.scatter(X, y, color = 'blue') 

plt.plot(X, lin2.predict(poly.fit_transform(X)), color = 'red') 
plt.title('Polynomial Regression') 


plt.show() 

# Predicting a new result with Polynomial Regression 
lin2.predict(poly.fit_transform(X_predict))
 

Для степени 2 результаты были

 array([[ 32067.76147835],
       [150765.87808383],
       [274174.84800471]])
 

Для степени 5 результаты были

 array([[  10934.83739791],
       [ 621503.86217946],
       [2821409.3915933 ]])
 

После поиска по уравнению я смог подогнать данные к уравнению «секунды = a * exp (b * N) смещение» с установленными параметрами a = 2.5066753490350954E-05, b = 7.2292352155213369E-01 и смещение = 1.6562196782144639E 01, что дает RMSE = 0.2542 и R-квадрат =0,99999. Эта комбинация данных и уравнений чрезвычайно чувствительна к начальным оценкам параметров. Как вы можете видеть, он должен интерполироваться с высокой точностью в пределах диапазона данных. Поскольку уравнение простое, оно, вероятно, будет экстраполироваться далеко за пределы диапазона данных. Насколько я понимаю ваше описание, если используется другое компьютерное оборудование или если алгоритм взлома распараллелен, то это решение не будет соответствовать этим изменениям.

Поскольку эта программа используется для взлома, она может использовать какую-то грубую силу, что приводит к экспоненциальному времени выполнения, поэтому гораздо лучше найти решение как

y = a b * c ^ n

например:

16.38 2.01 ^ n / 20000

Вы можете попробовать прогнозировать log(time) вместо time в LinearRegression