Как определить трудоемкость составленного алгоритма?

[Fides]

Помогите, кто знает, как определить трудоемкость составленных алгоритмов?! Необходимо для сравнения, кто оптимальнее..

[AlexDem]

Если грубо - надо посчитать вложенные циклы. По сути трудоёмкость - это оценка функции роста количества итераций при линейном приращении объема данных.

Например, если при увеличении размера входного массива в 2 раза количество итераций алгоритма по его обработке возрастёт в 4 раза, то это - квадратичная зависимость $O(n^2)$.

Можно эту функцию получить и экспериментально - нужно просто замерить время работы алгоритма на различных объёмах входных данных и построить график.

Может оказаться, что алгоритм с большей трудоёмкостью будет более эффективен на небольших объемах данных, поскольку коэффициенты при её расчёте обычно опускаются и считается предельная оценка при $n \to \infty$. Например, алгоритм $O(2 * n^2)$ будет явно эффективнее на небольших объемах, чем $O(1000 * n)$. Поэтому Вам, возможно, будет интереснее замерить реальную производительность и получить графическую зависимость экспериментально.

[незваный гость]

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

[Fides]

незваный гость писал(а):

:evil:
Вас интересует трудоемкость (т.е. сколько усилий должен затратить программист на разработку алгоритма) или сложность (как долго комп будет щелкать, пока выдаст ответ)? На эти вопросы ответы разные… и занимаются ими разные дисциплины.

По сути мне только лишь надо показать сложность.. т.е. какой алгоритм меньше занимает памяти, да и вообще быстрее работает... на пальцах то объяснить не сложно, но вот документально подтвердить..

Поискав по интернету.. много чего нашла, но, честно, доскональный анализ мне не нужен..
просто надо быстро и явно показать разницу...

Добавлено спустя 5 минут 7 секунд:

AlexDem писал(а):

Может оказаться, что алгоритм с большей трудоёмкостью будет более эффективен на небольших объемах данных, поскольку коэффициенты при её расчёте обычно опускаются и считается предельная оценка при $n \to \infty$. Например, алгоритм $O(2 * n^2)$ будет явно эффективнее на небольших объемах, чем $O(1000 * n)$.

Вот как раз так и у меня приведен пример маленькой размерности, но разработан он для больших.. и в этой сути мне и необходимо сравнение..

[AlexDem]

незваный гость писал(а):

Вас интересует трудоемкость (т.е. сколько усилий должен затратить программист на разработку алгоритма) или сложность (как долго комп будет щелкать, пока выдаст ответ)?

Вопрос терминологии... По-моему, трудоёмкость алгоритма - то же, что и вычислительная сложность. А первое - трудоёмкость разработки, т.е. как долго программист будет щёлкать, пока выдаст программу

Fides писал(а):

Вот как раз так и у меня приведен пример маленькой размерности, но разработан он для больших.. и в этой сути мне и необходимо сравнение..

Ну и?... В чём загвоздка? Если алгоритм сложный, то может проще его реализовать, а трудоёмкость измерить?

Вот у этого трудоёмкость - $O(n)$:

void fun(int array[], int size) {
    int i;

    for (i = 0; i < size; i++) {
        array[i]++;
    }
}

Вот у этого трудоёмкость - $O(n^2)$:

void fun(int array[], int size) {
    int i, j;

    for (i = 0; i < size; i++) {
        for (j = 0; j < size; j++) {
            array[i] += array[j];
        }
    }
}

Трудоёмкость второго выше, поскольку на каждый элемент массива выволняется перебор элементов этого же массива во вложенном цикле. Поэтому во втором случае на каждую из $n$ итераций охватывающего цикла приходится $n$ итераций вложенного цикла. Итого $n * n = n^2$. Для оценки трудоёмкости достаточно взять кусок алгоритма с наибольшей вложенностью циклов.

На простых алгоритмах всё просто, но даже посчитать трудоёмкость быстрой сортировки $n\log(n)$ уже будет сложнее.

[незваный гость]

AlexDem писал(а):

Вопрос терминологии...

И правильного ее использования. Трудоемкость (как сложность) я нигде не встречал. (Мы можем, кстати, называть производную — наклоном.)

AlexDem писал(а):

На простых алгоритмах всё просто, но даже посчитать трудоёмкость быстрой сортировки $n\log(n)$ уже будет сложнее.

Не очень удивительно. Поскольку хорошо известно, что для быстрой сортировки ${\rm O}(n \ln n)$ — лишь сложность в среднем. Гарантированная сложность — ${\rm O}(n^2)$.

Кроме того, можно говорить о сложности по памяти, амортизированной сложности, …

[Fides]

Спасибо за то что откликнулись.. надеюсь не последний раз.. но так же надеюсь, что мне краснеть более не прийдется

[незваный гость]

Краснеть обычно приходится не когда не знаешь, а когда не хочешь узнать. Никто со знанием интеграла (и алгорифма быстрой сортировки) еще не родился…

[Fides]

незваный гость писал(а):

:evil:
Краснеть обычно приходится не когда не знаешь, а когда не хочешь узнать. Никто со знанием интеграла (и алгорифма быстрой сортировки) еще не родился…

ну.. я считаю, что для магистра прикладной математики и кибернетики - это стыдно!!

[AlexDem]

незваный гость писал(а):

:evil:

AlexDem писал(а):

Вопрос терминологии...

И правильного ее использования. Трудоемкость (как сложность) я нигде не встречал. (Мы можем, кстати, называть производную — наклоном.)

Термин "трудоёмкость алгоритма" существует и был употреблён вполне корректно. В этом легко можно убедиться, поискав словосочетание в поисковике. Вот, например, по одной из первых ссылок:

Цитата:

Трудоемкость алгоритма.
то же что Временная сложность.

Временная сложность
Time complexity
основной параметр, характеризующий алгоритм; определяется как число шагов, выполняемых алгоритмом в худшем случае, обычно рассматривается как функция размера задачи, представленной входными данными. Обычно под размером теоретико-графовой задачи понимается число вершин графа $n$, число дуг $m$ или пара $(n, m)$. Под шагом алгоритма понимается выполнение одной из команд некоторой гипотетической машины. Поскольку при таком определении шага сложность алгоритма зависит от конкретного вида машинных команд, во внимание принимается асимптотическая сложность, т.е. асимптотическая скорость увеличения числа шагов алгоритма, когда размерность задачи неограниченно растет. Ясно, что при двух произвольных "разумных" способах перевода алгоритма в последовательность машинных команд соответствующие сложности различаются не более чем на мультипликативную константу, а их скорость роста одинакова.<...>

Другое название - Вычислительная сложность. См. также Сложность РАМ.

Литература: Ахо-Хопкрофт-Ульман, Евстигнеев-Касьянов/94, Липский.

незваный гость писал(а):

AlexDem писал(а):

На простых алгоритмах всё просто, но даже посчитать трудоёмкость быстрой сортировки $n\log(n)$ уже будет сложнее.

Не очень удивительно. Поскольку хорошо известно, что для быстрой сортировки ${\rm O}(n \ln n)$ — лишь сложность в среднем. Гарантированная сложность — ${\rm O}(n^2)$.

Не думаю, что "в среднем" здесь корректное выражение, поскольку я не могу представить себе набор данных, на котором стандартный алгоритм быстрой сортировки работал бы эффективнее, чем $O(n\log(n))$ - для этого нужно разделить отрезок ровнее, чем пополам. Это, скорее, наилучшая оценка, к которой алгоритм устойчиво стремится.

Сложность $O(n^2)$ получается в том случае, если средний по счёту элемент диапазона на каждом шаге рекурсии будет оказываться близким к минимальному или максимальному значению диапазона. Вероятность этого на каждом шаге равна $\frac {2\delta n} n$, где $\delta n$ - малый интервал, принимаемый нами за неэффективное деление. На последовательности шагов эта вероятность будет равна $\prod{\frac {2\delta n} n}$, то есть - стремительно падает.

При $n \to \infty$ видим, что интервал $\delta n$ обязан быть конечным, иначе диапазон будет делиться на два бесконечных, то есть - пополам. Следовательно $\lim\limits_{n \to \infty}\prod{\frac {2\delta n} n} = 0$. Это есть вероятность того, что алгоритм продемонстрирует трудоёмкость $O(n^2)$.

Но и на конечных $n$ можно избежать любой вероятности появления $O(n^2)$, добавив предварительную логику поиска среднего элемента. Например, цикл поиска более-менее оптимального значения. Его сложность на каждом шаге будет не выше $O(n)$, и даже если он будет вызываться на каждом шаге рекурсии, по совокупности - не выше $O(n\log(n))$. Тогда общая сложность будет $O(2n\log(2n))$ с гарантией того, что трудоёмкость $O(n^2)$ не будет продемонстрирована никогда. В пределе $O(2n\log(2n))$ ничуть не хуже, чем $O(n\log(n))$.

[незваный гость]

AlexDem писал(а):

В этом легко можно убедиться, поискав словосочетание в поисковике. Вот, например, по одной из первых ссылок

Меня пока не убедило. Не всякий источник в сети — источник авторитетный. А что это за источник, я понять не сумел.

AlexDem писал(а):

Не думаю, что "в среднем" здесь корректное выражение

Для того, чтобы «в среднем» было корректным, не нужно, чтобы были примеры с меньшей сложностью. Достаточно, чтобы примеров с большей было достаточно мало.

AlexDem писал(а):

Это, скорее, наилучшая оценка, к которой алгоритм устойчиво стремится.

Что это значит — алгорифм (устойчиво) стремится к оценке?

AlexDem писал(а):

При $n \to \infty$ видим, что интервал $\delta n$ обязан быть конечным, иначе диапазон будет делиться на два бесконечных, то есть - пополам.

Я уже ничего не понимаю. Кто сортирует бесконечные массивы?

…

С каких это пор события с вероятностью 0 не реализуются? И с каких это пор оценка в худшем случае не зависит от событий с вероятностью 0?

AlexDem писал(а):

Но и на конечных $n$ можно избежать любой вероятности появления $O(n^2)$, добавив предварительную логику поиска среднего элемента. Например, цикл поиска более-менее оптимального значения.

Предъявите пример алгорифма, позволяющего избежать ${\rm O}(n^2)$ в худшем случае.

~~~~~~

Мне кажется, Вы все время путаете разные сложности и их определения. Сложность алгорифма — вполне формальное, математическое понятие. Оно имеет отношение к наблюдаемому поведению, но не прямым образом.

[AlexDem]

незваный гость писал(а):

Меня пока не убедило. Не всякий источник в сети — источник авторитетный. А что это за источник, я понять не сумел.

Ну не знаю, в принципе там были приведены ссылки на литературу. Если будет желание - посмотрите, убеждать Вас в чём либо у меня желания нет. Пускай будет сложность.

незваный гость писал(а):

Для того, чтобы «в среднем» было корректным, не нужно, чтобы были примеры с меньшей сложностью. Достаточно, чтобы примеров с большей было достаточно мало.

Так там кроме "патологии" $O(n^2)$ больше никаких примеров и нет. Такое же исключение, как деление на ноль. Поэтому и усреднять-то в принципе не по чему. Или Вы знаете другие примеры, неизвестные мне, на которых алгоритм демонстрирует иную сложность?

незваный гость писал(а):

Что это значит — алгорифм (устойчиво) стремится к оценке?

То, что (сложность) алгоритма стремится к полученной оценке $O(n\log n)$ означает, что с ростом $n$ количество ситуаций, при которых время работы алгоритма соответствует оценке $O(n^2)$, уменьшается. Под устойчивостью я имел ввиду монотонное стремление с ростом $n$ (по некоторой аналогии с устойчивостью динамических систем, возможно - неудачно).

незваный гость писал(а):

Я уже ничего не понимаю. Кто сортирует бесконечные массивы?

В приведённом мной определении значилось, что сложность расчитывается при неограниченном росте $n$:

Цитата:

Поскольку при таком определении шага сложность алгоритма зависит от конкретного вида машинных команд, во внимание принимается асимптотическая сложность, т.е. асимптотическая скорость увеличения числа шагов алгоритма, когда размерность задачи неограниченно растет.

Было бы удобнее, если бы Вы привели то формальное определение, на которое опираетесь Вы.

незваный гость писал(а):

С каких это пор события с вероятностью 0 не реализуются? И с каких это пор оценка в худшем случае не зависит от событий с вероятностью 0?

Они не реализуются хотя бы потому, что у нас нет бесконечного массива. Просто эта функция экспоненциально быстро убывает с ростом $n$, поэтому я и сказал, что сложность $O(n^2)$ - скорее "патология" типа деления на $0$.

незваный гость писал(а):

Предъявите пример алгорифма, позволяющего избежать $O(n^2)$ в худшем случае.

Давайте попробуем сломать вот такой вариант (здесь только поиск среднего, он должен стоять перед основным циклом):

#len   9
double value[len] = {-4, -3, -2, -1, 0, 1, 2, 3, 4};
int    count[len] = {0};
int    a, b, maxl, maxr;

for (a = 0; a < size; a++) {
    if (array[a] < value[0]) {
        count[1] += count[0];
        count[0] = 0;
        value[0] = array[a];
    }
    else if (array[a] > value[len - 1]) {
        count[len - 2] += count[len - 1];
        count[len - 1] = 0;
        value[len - 1] = array[a];
    }

    for (b = 0; b < len; b++) {
        if (array[a] <= value[b]) {
            count[b]++;
        }
        if ((b == 0) || (b == len - 1)) {
            continue;
        }
        if (count[b] > count[b - 1] + count[b + 1]) {
            value[b - 1] = (value[b - 1] + value[b]) / 2;
            value[b + 1] = (value[b + 1] + value[b]) / 2;

            count[b - 1] = (count[b - 1] + count[b]) / 2;
            count[b + 1] = (count[b + 1] + count[b]) / 2;

            count[b] /= 2;
        }
    }
}

a = 0;
b = len - 1;
maxl = 0;
maxr = 0;

while (a < b) {
    while ((a < b) && (maxl <= maxr)) {
        maxl += count[a];
        a++;
    }
    while ((a < b) && (maxr <= maxl)) {
        maxr += count[b];
        b--;
    }
}

middle = (value[a] + value[b]) / 2;

незваный гость писал(а):

Мне кажется, Вы все время путаете разные сложности и их определения. Сложность алгорифма — вполне формальное, математическое понятие. Оно имеет отношение к наблюдаемому поведению, но не прямым образом.

О том, что коэффициенты при расчёте сложности обычно опускаются, я сказал в самом начале темы. Но всё равно, не вижу причин, по которым нельзя было бы прикинуть сложность по реальному поведению программы.

Правка:
1. Изменил последний цикл анализа результирующего count
2. Добавил count[b] /= 2;

[незваный гость]

С приведенным алгоритмом буду разбираться чуть позже (с Вашего позволения).

Давайте начнем с простого:

Вычислительная сложность алгорифма в среднем: это усредненное по всем наборам входных данных количество операций, необходимое для выполнения задачи.

Вычислительная сложность алгорифма в худшем случае: это максимальное по всем наборам входных данных количество операций, необходимое для выполнения задачи.

Вычислительная сложность алгорифма в лучшем случае: это минимальное по всем наборам входных данных количество операций, необходимое для выполнения задачи.

Из этих определений сразу ясно, что вероятность «плохого» набора входных данных (на самом деле, поскольку мы имеем дело с перечислимым и перечисляемым множеством, уместнее говорить о количестве, а не о вероятности) не влияет на оценку в худшем случае: пока «плохие» данные существуют, они портят картину. Из этого же определения следует, что в лучшем случае правильная быстрая сортировка демонстрирует линейную скорость (сортировка массива из всех 0).

Далее: у меня вызывают серьезные сомнения (говоря формально) Ваши рассуждения о бесконечности. Все просто: все оценки всегда делаются для конечного $n$. То есть, мы может доказать, например, что для любого набора входных данных сложность сортировки лежит между $f(n)$ и $g(n)$. Тогда мы имеем право написать, что сложность в худшем случае ${\rm O}(f(n))$. Мы можем сосчитать количество операций, необходимое для сортировки всех наборов, и поделить его на количество наборов, Таким образом, мы получим сложность в среднем ${\rm O}(h(n))$. Заметьте, я нигде не рассуждал о вероятностях.

AlexDem писал(а):

Но всё равно, не вижу причин, по которым нельзя было бы прикинуть сложность по реальному поведению программы.

Прикинуть Вы можете, доказать — нет. Представьте себе алгорифм со сложностью $A n^2 + B n^3$, $A \gg B$. $A$ может быть так велико, что для любого практического набора данных (в пределах 8 часов вычислений) все квадратично. Но алгорифм остается кубическим.

Кроме того, иногда важна не только сложность в среднем, но и сложность в худшем случае. Маленькая вероятность? Это никого не волнует, если речь идет об управлении АЭС. (И, «Вы будете долго смеяться, но» я сталкивался с подобными ошибками в системах реального времени, которые «выстрелили» у заказчика.)

~~~~~~~~~

$P.S.$ Может быть, я зря не сделал оговорку: Предъявите пример алгорифма, позволяющего избежать ${\rm O}(n^2)$ в худшем случае, и не ухудшающего время в среднем.. Если Вы меня ловите на этом, приношу Вам свои извинения.

$P.P.S.$Быстрый тест для любых Ваших рассуждений: как будет работать Ваш алгорифм при всех данных равных? (Я знаю, правильный вариант быстрой сортировки с этим легко справляется. Но не любой.)

$P.^3 S.$ Простите, что я повторюсь: изучение алгорифмов — это очень формальная дисциплина. Это раздел математики, в котором получены совершенно интуитивно неочевидные результаты, в котором выше крыши открытых проблем (и за решение одной из них сулят лимон капусты). Дисциплина очень живая и динамичная: все время появляются новые результаты. Ваши рассуждения более или менее верны на бытовом уровне, но совершенно неформальны. Если Вас интересует формальная сторона вопроса, Вам нужно почитать хотя бы вводный курс в этот предмет.

$P.^4 S.$ Достал с полки Липского. В индексе нет трудоемкости, но есть сложность.

[AlexDem]

незваный гость писал(а):

Давайте начнем с простого:

С позиции данных Вами определений мои рассуждения, конечно, неверны. Но и сложность $O(n\log n)$ - тоже. Дело в том, что "количество операций" - понятие довольно запутанное. Каких операций? Если сортировать строки длины $k$ (пусть они всегда сравниваются целиком), то она будет уже $O(kn\log_2 kn)$.

незваный гость писал(а):

Далее: у меня вызывают серьезные сомнения (говоря формально) Ваши рассуждения о бесконечности.

Возможно, но если не забыл - так нас учили "в школе".

незваный гость писал(а):

Прикинуть Вы можете, доказать — нет.

Доказать измерением отсутствие что-либо вообще невозможно, но вопрос о строгом доказательстве изначально и не стоял. Если знать узкие места алгоритма, то данные можно подобрать соответствующим образом. Либо прогнать на нескольких наборах. Для заданного вопроса этого, по-моему, достаточно...

незваный гость писал(а):

Кроме того, иногда важна не только сложность в среднем, но и сложность в худшем случае. Маленькая вероятность? Это никого не волнует, если речь идет об управлении АЭС. (И, «Вы будете долго смеяться, но» я сталкивался с подобными ошибками в системах реального времени, которые «выстрелили» у заказчика.)

Ну, в общем, да - с этим трудно не согласиться...

незваный гость писал(а):

P.S. Может быть, я зря не сделал оговорку: Предъявите пример алгорифма, позволяющего избежать $O(n^2)$ в худшем случае, и не ухудшающего время в среднем.. Если Вы меня ловите на этом, приношу Вам свои извинения.

У меня что-то такое ощущение, что это Вы меня ловите . Про время в среднем я нигде не говорил, поэтому такая оговорка была бы некорректной. Просто любой дополнительный цикл сложности не выше $O(n)$ увеличит время раза в два (мой - поболе), что полностью эквивалентно сравнению, скажем, 8-байтовых данных вместо 4-байтовых. Если принять, что сложность алгоритма от размера элемента данных не зависит, то и моя добавка не должна учитываться тоже.

незваный гость писал(а):

P.P.S.Быстрый тест для любых Ваших рассуждений: как будет работать Ваш алгорифм при всех данных равных? (Я знаю, правильный вариант быстрой сортировки с этим легко справляется. Но не любой.)

Ну, приведённый вариант на этом вроде как ляжет в последнем цикле анализа count, но если несколько докрутить под граничные условия, что в некотором диапазоне счётчик может быть нулевым, то справится. А алгоритм сортировки у меня под носом лежит такой:

void funQSort(
    dtype         *base[],
    const int      lenF,
    int            limL,
    const int      limH)
{
    int            eleL, eleH;
    dtype         *midd, *swap;

    while (limL < limH) {
        /* Initialize variables */
        eleL = limL;
        eleH = limH;
        midd = base[(eleL + eleH) >> 1];

        /* Compare rows */
        while (eleL < eleH) {
            /* Compare elements */
            while (memcmp(base[eleL], midd, lenF) < 0) {
                eleL++;
            }
            while (memcmp(base[eleH], midd, lenF) > 0) {
                eleH--;
            }

            /* Swap improper elements */
            if (eleL <= eleH) {
                swap = base[eleL];
                base[eleL] = base[eleH];
                base[eleH] = swap;
                eleL++;
                eleH--;
            }
        }

        /* Recurrent lower iteration */
        if (eleH > limL) {
            funQSort(base, lenF, limL, eleH);
        }

        /* Next higher iteration */
        limL = eleL;
    }
}

Добавлено спустя 11 минут 44 секунды:

незваный гость писал(а):

Если Вас интересует формальная сторона вопроса, Вам нужно почитать хотя бы вводный курс в этот предмет.

Нет, честно сказать, в данный момент не очень интересует... Лимон за $P=NP$? Пожалуй, есть более простые способы разбогатеть

незваный гость писал(а):

Достал с полки Липского. В индексе нет трудоемкости, но есть сложность.

Этому нас тоже "учили в школе". Возможно, термин имеет ограниченное хождение. Зря говорить я бы не стал.

[незваный гость]

AlexDem писал(а):

У меня что-то такое ощущение, что это Вы меня ловите.

Нет. Просто без этой оговорки мое утверждение неверно.

AlexDem писал(а):

Просто любой дополнительный цикл сложности не выше $O(n)$ увеличит время раза в два (мой - поболе),…

Увеличение в ограниченное число раз (${\rm O}(1)$) нас не волнует — мы говорим об ${\rm O}$.

AlexDem писал(а):

Дело в том, что "количество операций" - понятие довольно запутанное. Каких операций?

Элементарных. То есть, тех, что мы считаем элементарными шагами алгорифма. Например, сравнения и перестановки элементов (общепринятые единицы в задачах сортировки).