fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int main() {
  5. 	// Complexity - Big O
  6. 	// Seberapa banyak operasi yg dilakukan/runtime berubah
  7. 	//   saat ada perubahan input
  8. 	// contoh: bubble sort vs quick sort
  9. 	/*
  10. 	int n, data[1000001];					// O(1)
  11. 	cin >> n;								// O(1)
  12. 	for(int i = 0; i < n; i++)				// O(n)
  13. 		cin >> data[i];
  14. 	for(int i = 0; i < n; i++)				// O(n^2)
  15. 		for(int j = 1; j < n; j++)
  16. 			if(data[j] < data[j-1]) {
  17. 				int tmp = data[j];
  18. 				data[j] = data[j-1];
  19. 				data[j-1] = tmp;
  20. 			}
  21. 	n = 10 -> op = 1+1+10+90 = 102
  22. 	n = 100 -> op = 1+1+100+9900 = 10002
  23. 	n = n -> op ~ n^2 -> O(n^2)
  24. 	*/
  25. 	// Rule of Thumb: 10^8 op = 1s
  26. 	// Big O = O(n^2)
  27. 	/*
  28. 	O(n)
  29. 	n = 10 -> rt = 1ms
  30. 	n = 100 -> rt = 10ms
  31. 	n = 1000 -> rt = 100ms
  32. 	..
  33.  
  34. 	O(n^2)
  35. 	n = 10 -> rt = 1ms
  36. 	n = 100 -> rt = 100ms
  37. 	n = 1000000 -> rt = 10^10ms
  38. 	*/
  39.  
  40. 	// 4 Paradigm overview
  41. 	/*
  42. 	// n <= 200000, data[i] <= 10^6
  43. 	int data = {10, 7, 3, 5, 8, 6, 9, 11}, n = 8;
  44. 	//                 ^  ^  ^     ^   
  45. 	// 3, 5, 8, 9
  46.  
  47. 	// 1. Cari bilangan terbesar & terkecil dari array data. O(n)
  48. 	maks = data[0];
  49. 	for(int i = 1; i < n; i++)
  50. 		if(data[i] > maks)
  51. 			maks = data[i];
  52. 	// 2. Cari bilangan terbesar urutan ke-k dari array data. (k<=n)
  53. 	// Pendekatan pertama: sort O(n^2) -> Time Limit Exceeded
  54. 	// Pendekatan kedua: Cari bil terbesar, lalu hapus.
  55. 	//                   Cari bil kedua terbesar, lalu hapus.
  56. 	//                   Ulangi sampai bil ke-(k-1) terbesar & hapus.
  57. 	//                   Cari bil ke-k terbesar. -> O(n*k) = O(n^2)
  58. 	for(int i = 0; i < k; i++)
  59. 		for(int j = 0; j < n; j++)
  60. 			...
  61. 	// Pendekatan yang tepat: sort O(n log n)
  62. 	// 3. Cari selisih terbesar dalam array data.
  63. 	// Pendekatan complete search -> O(n^2) -> TLE
  64. 	for(int i = 0; i < n; i++)
  65. 		for(int j = i+1; j < n; j++)
  66. 			if(maks < abs(data[i]-data[j]))
  67. 				maks = abs(data[i]-data[j]);
  68. 	// loop = (n-1)+(n-2)+...+1+0 = n*(n-1)/2 = (n^2-n)/2
  69. 	// Greedy -> O(n)
  70. 	// 4. Cari panjang LIS = Longest Increasing Subsequence di array data.
  71. 	// Dynamic Programming
  72. 	// - banyak subsoal yang overlap, yang seharusnya bisa dikerjakan
  73. 	//   sekali saja
  74. 	// 9! = 362880
  75. 	// 10! = 362880*10 = 3628800
  76. 	// 11! = 3628800*11 = 39916800
  77. 	// teknik memoization
  78. 	*/
  79.  
  80. 	// Complete Search
  81. 	// Iterative = loop
  82. 	// Recursive = fungsi rekursif
  83. 	// Pruning -> tidak melanjutkan proses yang pasti gagal
  84. 	/* 8 ratu di papan catur -> 8 Queens problem
  85. 	o..o..o.
  86. 	.o.o.o..
  87. 	..ooo...
  88. 	oooQoooo
  89. 	..ooo...
  90. 	.o.o.o..
  91. 	o..o..o.
  92. 	...o...o
  93.  
  94. 	C(64, 8) = terlalu besar
  95.  
  96. 	1.......
  97. 	..2.....
  98. >	....3...
  99. 	........
  100. 	........
  101. 	........
  102. 	........
  103. 	........
  104. 	8^7
  105. 	*/
  106.  
  107. 	/*
  108. 	// Divide & Conquer -> harus terurut
  109. 	// linear search -> per langkah -1 -> O(n)
  110. 	// binary search -> per langkah /2 -> O(log n)
  111.  
  112. 	// Soal: cari sebuah nilai dalam array yg terurut
  113. 	// cari = 10
  114. 	// {1, 1, 2, 2, 2, 4, 5, 6, 6, 9, 10, 13, 17, 22, 23}
  115. 	//           |-------------------------------------|
  116. 	// data terurut: i1 <= i2 -> data[i1] <= data[i2]
  117. 	int data[] = {1, 1, 2, 2, 2, 4, 5, 6, 6, 9, 10, 13, 17, 22, 23}, n = 15;
  118. 	int cari = 10;
  119.  
  120. 	// linear search
  121. 	for(int i = 0; i < n; i++)
  122. 		if(data[i] == cari)
  123. 			cout << cari << " ditemukan di index " << i << endl;
  124.  
  125. 	// binary search
  126. 	// {1, 1, 2, 2, 2, 4, 5, 6, 6, 9, 10, 13, 17, 22, 23}
  127. 	//  |--------------------|-------------------------|
  128. 	//                          |----------|-----------|
  129. 	//                          |--|---|
  130. 	//                                 |
  131. 	// dalam 1 langkah -> search space berkurang jadi 1/2 nya
  132. 	// dalam x langkah -> search space berkurang jadi 1/2^x nya
  133. 	// n = 2^x -> x = log2 n
  134. 	// ukuran search space = n -> banyak langkah = log2 n = log n
  135. 	int lo = 0, hi = n-1, mid;
  136. 	while(lo < hi) {
  137. 		mid = (lo+hi)/2;
  138. 		if(data[mid] > cari)
  139. 			hi = mid-1;
  140. 		else if(data[mid] < cari)
  141. 			lo = mid+1;
  142. 		else
  143. 			lo = hi = mid;
  144. 	}
  145. 	cout << cari << " ditemukan di index: " << lo << endl;
  146. 	*/
  147.  
  148. 	/*
  149. 	// Bisection method / Binary Search The Answer (BSTA)
  150. 	// 0 <= x < PI/2, sin(x) = increasing
  151. 	// x1 < x2 -> sin(x1) < sin(x2)
  152. 	// sin(x) = 0.75 -> x = arcsin(0.75)
  153. 	double PI = acos(-1);
  154. 	// cos(180) = cos(PI) = -1
  155. 	// acos(-1) = PI
  156.  
  157. 	double y = 0.75;
  158. 	double lo = 0, hi = PI/2, mid;
  159. 	while(hi-lo > 1e-12) {	// 1.23e-4 = 1.23*10^-4
  160. 		mid = (lo+hi)/2;
  161. 		cout << lo << " " << mid << " " << hi << endl;
  162. 		if(sin(mid) > y)
  163. 			hi = mid;
  164. 		else if(sin(mid) < y)
  165. 			lo = mid;
  166. 	}
  167. 	cout << "arcsin(" << y << ") = " << lo << endl;
  168. 	*/
  169.  
  170. 	// Greedy
  171. 	// Lihat contoh di PKD
  172.  
  173. 	// Dynamic Programming
  174. 	// N = a_k + a_i_2 + ... + a_i_m -> m minimal = f(N)
  175. 	// (N-a_k) = a_i_2 + ... + a_i_m -> m minimal = f(N-a_k)
  176.  
  177. 	return 0;
  178. }
Success #stdin #stdout 0s 5304KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/2ZVaKd
language:
C++ (gcc 8.3)
created:
16 days ago
visibility:
public

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!