Обозначение большого O

Фрагмент отличного поста на форуме, который учит нас, как легко вычислять Big 0

Некоторые основные правила:

1. Вложенные циклы перемножаются.
2. Добавляются последовательные петли.
3. Сохраняется только самый большой член, все остальные отбрасываются.
4. Константы отбрасываются.
5. Условные проверки постоянны (т.е. 1).
6. Быстрая метрика, чтобы увидеть, является ли цикл log n, состоит в том, чтобы увидеть, как счетчик увеличивается по отношению к общему количеству элементов.

Примеры:

int i = 0;
if(i < 1) {
  // do stuff
}

O(1) Константа

for(int i = 0; i < n; i++) {
	//do stuff
}

линейный: п

for(int i = 0; i < 2*n; i++) {
	//do stuff
}

линейный: 2*n -> n

for(int i = 0; i < n; i++) { // linear
	for(int j = 0; j < n; j++){ // linear
		//do swap stuff, constant time
	}
}

квадратичный: n (внешний) * n (внутренний) -> n²

for(int i = 0; i < n; i++) { // linear
	for(int j = 0; j < i; j++){ // linear
		//do swap stuff, constant time
	}
}

квадратичный: n (внешний) * (n-1) (внутренний наихудший случай) -> n²

for(int i = 0; i < n; i *= 2) { 
	//do stuff
}

журнал (n)

for(int i = 0; i < n; i++) { // linear
	for(int j = 1; j < n; j *= 2){ // log (n)
		//do constant time stuff
	}
}

п*лог(п)

Дополнительные ссылки

Порядки общих функций