fork download 
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <vector>
  4. #include <chrono>
  5. using namespace std;
  6. using namespace std::chrono;
  7.  
  8. vector<int> readArray() {
  9. 	int aSize;
  10. 	scanf("%d", &aSize);
  11. 	vector<int> a(aSize);
  12. 	for (int i = 0; i < aSize; i++)
  13. 		scanf("%d", &a[i]);
  14. 	return a;
  15. }
  16.  
  17. int random(int l, int r) {
  18. 	return l + rand() % (r - l + 1);
  19. }
  20.  
  21. vector<int> generateArray(int size) {
  22. 	vector<int> a(size);
  23. 	for (int i = 0; i < size; i++)
  24. 		a[i] = random(-100, 100);
  25. 	return a;
  26. }
  27.  
  28. int lisLength(vector<int> &a) {
  29. 	vector<int> length(a.size());
  30. 	int maxLength = 0;
  31. 	for (int i = 0; i < a.size(); i++) {
  32. 		length[i] = 1;
  33. 		for (int j = 0; j < i; j++) {
  34. 			if (a[j] < a[i] && length[i] < length[j] + 1)
  35. 				length[i] = length[j] + 1;
  36. 		}
  37. 		if (maxLength < length[i])
  38. 			maxLength = length[i];
  39. 	}
  40. 	return maxLength;
  41. }
  42.  
  43. double singleTimeTest(int size) {
  44. 	vector<int> a = generateArray(size);
  45. 	high_resolution_clock::time_point startTime = high_resolution_clock::now();
  46. 	lisLength(a);
  47. 	high_resolution_clock::time_point finishTime = high_resolution_clock::now();
  48. 	duration<double> elapsedTime = duration_cast<duration<double>>(finishTime - startTime);
  49. 	return elapsedTime.count();
  50. }
  51.  
  52. double multipleTimeTests(int size, int testsCount) {
  53. 	double totalTime = 0;
  54. 	for (int i = 0; i < testsCount; i++)
  55. 		totalTime += singleTimeTest(size);
  56. 	return totalTime / testsCount;
  57. }
  58.  
  59. void timeTestingTable() {
  60. 	printf("N\tT(N)\n");
  61. 	for (int n = 16; n <= 4096; n *= 2)
  62. 		printf("%d\t%lf\n", n, multipleTimeTests(n, 100));
  63. }
  64.  
  65. int main() {
  66. 	timeTestingTable();
  67. }
Success #stdin #stdout 3.21s 15240KB
comments ()
stdin 
Standard input is empty
stdout 
N	T(N)
16	0.000001
32	0.000002
64	0.000007
128	0.000028
256	0.000091
512	0.000354
1024	0.001470
2048	0.005998
4096	0.024195
https://ideone.com/hDwfGb
language:
C++ (gcc 8.3)
created:
7 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!