Здравствуйте, hpux100, Вы писали:

H>Спрашивают по большей части на собеседованиях, но практически тоже имеет смысл знать.
H>Например поиск в неотсортированном массиве имеет линейную сложность это очевидно, а вот например поиск в отсртированном (или сбалансированном дереве) логарифмическую, но непонятно как подсчитать.
H>Подскажите есть ли общие приципы подсчета сложности алгоритмов?

Для простоты можно считать, что есть следующие оценки: константа (единица), log(N), N, N^2, N в какой-либо степени (редко), N^N (ни разу не встречал).
Общий принцип такой: прикидываешь, во сколько раз увеличится количество итераций алгоритма, если увеличить N в четыре раза. Не увеличивается — константа. Увеличится в два раза — вроде как корень, но у нас только log(N), так что значит log(N). В четыре раза — сложность N. В шестнадцать раз — N^2 и т.д.
Итерация — это либо один проход цикла, либо один вызов рекурсивной функции.

Спрашивают по большей части на собеседованиях, но практически тоже имеет смысл знать.
Например поиск в неотсортированном массиве имеет линейную сложность это очевидно, а вот например поиск в отсртированном (или сбалансированном дереве) логарифмическую, но непонятно как подсчитать.
Подскажите есть ли общие приципы подсчета сложности алгоритмов?

Здравствуйте, hpux100, Вы писали:

H>Спрашивают по большей части на собеседованиях, но практически тоже имеет смысл знать.
H>Например поиск в неотсортированном массиве имеет линейную сложность это очевидно, а вот например поиск в отсртированном (или сбалансированном дереве) логарифмическую, но непонятно как подсчитать.
H>Подскажите есть ли общие приципы подсчета сложности алгоритмов?

http://th-algoritmov.narod.ru/5.htm

http://www.structur.h1.ru/ocenka.htm

Здравствуйте, hpux100, Вы писали:
H>Например поиск в неотсортированном массиве имеет линейную сложность это очевидно, а вот например поиск в отсртированном (или сбалансированном дереве) логарифмическую, но непонятно как подсчитать.
H>Подскажите есть ли общие приципы подсчета сложности алгоритмов?
если кол-во элементов дерева вырастет в два раза на сколько шагов больше надо будет сделать? на 1 шаг только — дальше мы получим поддерево в с два раза меньшим кол-вом элементов. а если увеличим в 2^15 раз? тогда время работы увеличится на 15 шагов, log(2^15) равен 15 log(2), получается логарифмический рост времени от числа элементов

Здравствуйте, hpux100, Вы писали:

H>Спрашивают по большей части на собеседованиях, но практически тоже имеет смысл знать.
H>Например поиск в неотсортированном массиве имеет линейную сложность это очевидно, а вот например поиск в отсртированном (или сбалансированном дереве) логарифмическую, но непонятно как подсчитать.
H>Подскажите есть ли общие приципы подсчета сложности алгоритмов?

Понимаю, что это будет чересчур усложненный ответ на вопрос, но кому-нибудь будет полезно...

Возьмем задачу о поиске числа в отсортированном массиве. Обозначим сложность алгоритма двоичного поиска как T(n). В этом алгоритме на каждой итерации мы выполняем сравнение с медианным элементом (то есть выполняем некоторое константное количество операций), и переходим к той же самой задаче, но уже на половине исходного массива. Это мы можем записать в виде рекуррентного соотношения:
T(n) = T(n/2) + O(1)

Так вот, для решения рекуррентных соотношений вида
T(n) = a*T(n/b) + f(n) (a >= 1, b > 1) может быть использована Master theorem (лучше, конечно, почитать в CLRS, там все четче и понятнее, чем в википедии). Она гласит следующее:
1. Если f(n) = O(n^(logb(a)-e)), где e > 0, то T(n) = Θ(n^logb(a))
2. Если f(n) = Θ(n^(logb(a)) * log[k](n)), то T(n) = Θ(n^logb(a) * log[k+1](n)) (log[0](n) = 1, log[1](n) = log(n), log[2](n) = log(log(n)) и т.д.)
3. Если f(n) = Ω(n^(logb(a)+e)), где e > 0, то T(n) = Θ(f(n))

Применим эту теорему для примера к бинарному поиску (из пушки по воробьям ):
T(n) = T(n/2) + С
В данном случае a = 1, b = 2, logb(a) = 0, f(n) = C
f(n) = Θ(n^0 * log[0](n)), то есть у нас второй случай, следовательно T(n) = Θ(n^0 * log(n)) = Θ(log(n))

Здравствуйте, hpux100, Вы писали:

H>Подскажите есть ли общие приципы подсчета сложности алгоритмов?

Совсем недавно пролистывал "Программист-прагматик".

Оценка с точки зрения здравого смысла

Можно оценить порядок многих базовых алгоритмов с точки зрения здравого смысла.

• Простые циклы. Если простой цикл выполняется от 1 до n, то алгоритм, скорее всего, является O(n) – время находится в линейной зависимости от n. Примерами этого являются исчерпывающий поиск, поиск максимального элемента в массиве и генерация контрольной суммы.

• Вложенные циклы. Если вы помещаете один цикл в другой, то ваш алгоритм становится O(m*n), где m и n – пределы этих двух циклов. Обычно это свойственно простым алгоритмам сортировки, типа пузырьковой сортировки, где внешний цикл поочередно просматривает каждый элемент массива, а внутренний цикл определяет местонахождение этого элемента в результирующем массиве. Подобные алгоритмы сортировки чаще всего стремятся к O(n^2).

• Алгоритм двоичного поиска. Если алгоритм делит пополам набор элементов, который он рассматривает всякий раз в цикле, то скорее всего он логарифмический O(lg(n)) (см. упражнение 37). Двоичный поиск в упорядоченном списке, обход двоичного дерева и поиск первого установленного бита в машинном слове могут быть O(lg(n)).

• Разделяй и властвуй. Алгоритмы, разбивающие входные данные на разделы, работающие независимо с двумя половинами и затем комбинирующие конечный результат, могут представлять собой O(nlg(n)). Классическим примером является алгоритм быстрой сортировки, который делит входной массив пополам и затем проводит рекурсивную сортировку в каждой из половин. Хотя технически он и является O(n^2), поскольку его поведение ухудшается при обработке упорядоченных данных, но среднее время быстрой сортировки составляет O(nlg(n)).

• Комбинаторика. При использовании алгоритмов в решении любых задач, связанных с перестановкой, время их выполнения может выйти из-под контроля.
Это происходит потому, что задачи о перестановке включают вычисления факториалов (существует 5! = 5*4*3*2*1 = 120 перестановок цифр от 1 до 5). Возьмем за основу время выполнения комбинаторного алгоритма для пяти элементов; для шести элементов времени потребуется в шесть раз больше, а для семи – в 42. Примерами этого являются алгоритмы решения многих известных сложных задач – о коммивояжере, об оптимальной упаковке предметов в контейнер, о разделении набора чисел таким образом, что сумма каждого отдельного набора одинакова и т. д. Во многих случаях для сокращения времени выполнения алгоритмов данного типа в определенных прикладных областях используются эвристические подходы.

Здравствуйте, hpux100, Вы писали:

H>Спрашивают по большей части на собеседованиях, но практически тоже имеет смысл знать.
H>Например поиск в неотсортированном массиве имеет линейную сложность это очевидно, а вот например поиск в отсртированном (или сбалансированном дереве) логарифмическую, но непонятно как подсчитать.
H>Подскажите есть ли общие приципы подсчета сложности алгоритмов?
Почитай про это вторую главу книги Анания Левитина "Алгоритмы. Введение в разработку и анализ". По-моему там довольно хорошо описано.