Time complexity

А сам не хочешь своё дз делать?

> О(n*sqrt4(n))

Хм, а как ты такое высчитал? Тут вроде все очевидно: while (j>0) j = j/4 - это O(log4(j)), j = n, плюс внешний цикл, и получаешь O(n*log4(n)). O(n*log4(n)) это тоже самое что и O(n*log n) в силу того, как определено O. Можешь использовать тот вариант, который тебе больше нравится.

j(k) = j(k-1) / 4 = j(0) * (1/4) ** k.

j(0) / j(k) = 4 ** k, k ~ log4(j(0)/j(k)) ~ log4(n)

Про внешний цикл понятно, что это n. С внутренним что-то тупанул. А как, например, может выглядеть сложность О(sqrt(n)). Такое вообще бывает?

2dimon555

Был бы рад, еслиб это было ДЗ. Учусь по самоучителю, так что сдавать некому :)

> сложность О(sqrt(n)). Такое вообще бывает?

Это просто O(n^1/2). Почему бы и нет? :-)

Спасибо. Но я говорю про то, как это будет реализовано в виде кода. while(j > 0) j = sqrt(j); Я правильно понял? В таком случае можно сказать что O(sqrt(n))?

Неправильно, при j !=0 это будет вообще бесконечный цикл.

И даже если это исправить, то сложность все равно будет не такая, а вот такая: http://oeis.org/A001069

По ходу нет обозначения для этой функции.

>Почему в данном варианте сложность О(n*log4(n)), а не О(n*sqrt4(n))? Почему вообще присутствует log4, ведь при потсчете константы опускаются и должно, по идее, выйти O(n*log n).

Они не то чтобы опускаются, на них пофиг. O(f(x)) = O(a*f(x)) для любой константы a=/=0

>Про внешний цикл понятно, что это n. С внутренним что-то тупанул. А как, например, может выглядеть сложность О(sqrt(n)). Такое вообще бывает?

Ну... допустим тривиальный алгоритм проверки числа на простоту - делить на все натуральные числа от 2 до квадратного корня числа.

> while(j > 0) j = sqrt(j); Я правильно понял? В таком случае можно сказать что O(sqrt(n))?

Нет. О - это асимптотическая оценка. Время выполнения процедуры g(n) есть O(n^1/2) означает, что выполняя некую процедуру g, понадобится не более С*n^1/2 шагов для всех больших n, где С - некая константа. То есть это именно асимптота: время процедуры g будет всегда меньше или равно C*n^1/2. Если что-то имеет сложность O(n^1/2), можно сказать что оно имеет сложность и O(n), или даже O(n^2), просто это более грубые оценки.

Всем спасибо за объяснения. Разобрался :)