1) Сложность алгоритмов 
O(n) 
Были входные данные - массив на н переменных, и мы просто ввели его 

O(5 * n^2 + n * 8 + 137) - O(n^5)
O(8 * n) = O(n) = O(1000 * n)
O(1000) = O(1)

В с++ все операции с числами - это константа
Операции - это что-то элементарное

В с++ выполняется 1е8 - 100 миллионов операций в секунду
x++ - очень быстро 
cin >> x - долгая операция; 

n <= 1e5; O(n^2)


2)Сортировка 

a[0]..a[n - 1] - нам ввели массив на n элементов

Хотим переставить его элементы так, чтобы a[0] <= ... <= a[n - 1]

2.1)
Сортировка пузырьком:

a = [1, 5, 8, 2, 3, 2]

1)a = [1, 5, 2, 3, 2, 8]
2)a = [1, 2, 3, 2, 5, 8]
3)a = [1, 2, 2, 3, 5, 8]

Основная операция - стоим в i-м элементе, смотри на следующий, если он меньше, чем наш, то меняем, 
и переходим к i+1-му 

for (i = 0; i < n; i++){
	for (j = 0; j < n - 1; j++){
		if (a[j + 1] < a[j]){
			swap(a[j + 1], a[j]);
		}
	}
}

Сложность - O(n^2)

for (i = 0; i < n - 1; i++){
	for (j = 0; j < n - 1 - i; j++){
		if (a[j + 1] < a[j]){
			swap(a[j + 1], a[j]);
		}
	}
}

n + (n - 1) + ... + 1 + ... + 0 = n * n / 2 = O(n^2 / 2) = O(n^2)

a_1, a_2, ..., a_n 
a_1 
a_2 = a_1 + d 
a_3 = a_2 + 2 * d 

S = a_1 + a_2 + ... + a_n =  a_1 + (a_1 + d) + ... + (a_1 + (n - 2) * d) + (a_1 + (n - 1) * d) = 
(a_1 + a_n) * n / 2 


2.2)Сортировка выбором 


a = [1, 5, 8, 2, 3, 2]
1 итерация - найти максимум и поставить его в конец
for (i = 0; i < n; i++){
	int ma = 0; int ind;
	for (j = 0; j < n; j++){
		if (a[j] > ma){
			ma = a[j]; ind = j;
		}
	}
	swap(a[n - 1 - i], a[ind]);
}

2.3)Сортировка вставками

              
a = [1, 1, 5, 2, 3, 5]
a = [1, 2, 3, 4]

for (i = 0; i < n; i++){
	for (j = i - 1; j > -1; j++){
		if (a[j + 1] < a[j]){
			swap(a[j + 1], a[j]);
		}
		else{
			break;
		}
	}
}

a = [4, 3, 2, 1]
a = [4, 3, 2, 1]
a = [3, 4, 2, 1]
a = [2, 3, 4, 1]
a = [1, 2, 3, 4]

Сложность = 1 + 2 + ... + (n - 1) = O(n^2)

a = [n, n - 1, ..., 1]

O большое - <=

2.4)Сортировка подсчетом - O(n + C), C - макс.число

a[0]..a[n - 1] 
Пусть нам известно, что a[i] <= C \forall i

Допустим, a[i] <= 1e5 

a = [1, 5, 2, 3, 4, 3, 1, 5]

Заведем вспомогательный массив p[0]..p[C - 1] - p[C]


И тогда пусть p[i] - количество вхождений числа i в наш массив a 



c = 1e9;

int a[0]..a[n - 1];
vector<int> p(C);

for (i = 0; i < n; i++){
	p[a[i]]++;
}

vector<int> b(n);

int ind = 0;
for (i = 0; i < C; i++){
	for (j = 0; j < p[i]; j++){
		b[ind] = i;
		ind++;
	}
}