#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <chrono>
using namespace std;
using namespace std::chrono;
vector<int> readArray() {
int aSize;
scanf("%d", &aSize);
vector<int> a(aSize);
for (int i = 0; i < aSize; i++)
scanf("%d", &a[i]);
return a;
}
int random(int l, int r) {
return l + rand() % (r - l + 1);
}
vector<int> generateArray(int size) {
vector<int> a(size);
for (int i = 0; i < size; i++)
a[i] = random(-100, 100);
return a;
}
int lisLength(vector<int> &a) {
vector<int> length(a.size());
int maxLength = 0;
for (int i = 0; i < a.size(); i++) {
length[i] = 1;
for (int j = 0; j < i; j++) {
if (a[j] < a[i] && length[i] < length[j] + 1)
length[i] = length[j] + 1;
}
if (maxLength < length[i])
maxLength = length[i];
}
return maxLength;
}
double singleTimeTest(int size) {
vector<int> a = generateArray(size);
high_resolution_clock::time_point startTime = high_resolution_clock::now();
lisLength(a);
high_resolution_clock::time_point finishTime = high_resolution_clock::now();
duration<double> elapsedTime = duration_cast<duration<double>>(finishTime - startTime);
return elapsedTime.count();
}
double multipleTimeTests(int size, int testsCount) {
double totalTime = 0;
for (int i = 0; i < testsCount; i++)
totalTime += singleTimeTest(size);
return totalTime / testsCount;
}
void timeTestingTable() {
printf("N\tT(N)\n");
for (int n = 16; n <= 4096; n *= 2)
printf("%d\t%lf\n", n, multipleTimeTests(n, 100));
}
int main() {
timeTestingTable();
}