Подсчет примитивных операций и расчет нотации Big-O

Я написал фрагмент java-кода, который при задании массива (arrayX) вычисляет средние префиксы этого массива и выводит их в другой массив (arrayA). Я должен подсчитать примитивные операции и вычислить нотацию Big-O (я предполагаю, что это общее количество вычислений). Я включил java-код и то, что я считаю количеством примитивных операций рядом с каждой строкой, но я не уверен, правильно ли я их подсчитал. Заранее спасибо и извините за мою неопытность, мне трудно это понять :)

double [] arrayA = new double [arrayX.length]; *(3 Operations)*

    for (int i = 0; i < arrayX.length; ++i) *(4n + 2 Operations)* 
    {
        double sum = arrayX[i]; *(3n Operations)*

        for (int j = 0; j < i; ++j) *(4n^2 + 2n Operations)*
        {
            sum = sum + arrayX[j]; *(5n^2 Operations)*
        }
        arrayA[i] = sum/(i+1); *(6n Operations)*
    }
    return arrayA; *(1 Operation)*

Общее количество операций: 9n^2 +15n + 6


java algorithm counting primitive operations
person Phillip    schedule 12.11.2014    source источник
comment
У вас правильная идея, но фундаментальная концепция нотации Big-O заключается в том, что нас интересует порядок операций, а не буквальное количество. Этот вопрос может помочь пролить свет на концепцию.   -  person x4nd3r    schedule 13.11.2014

Ответы (1)


arrow_upward
3
arrow_downward

Я не думаю, что существует какое-либо стандартное определение того, «что представляет собой примитивную операцию». Я предполагаю, что это задание класса; если ваш инструктор дал вам подробную информацию о том, какие операции считать примитивными операциями, то придерживайтесь этого, иначе я не думаю, что он может обвинить вас в том, как вы их считаете, если у вас есть разумное объяснение.

Что касается внутреннего цикла:

for (int j = 0; j < i; ++j)

обратите внимание, что общее количество выполнений цикла равно не n2, а 0+1+2+...+(n-1) = n(n-1)/2. Так что ваши расчеты, вероятно, неверны.

Обозначение Big-O на самом деле не является «общим количеством вычислений»; грубо говоря, это способ оценить, как растет количество вычислений при росте n, говоря, что количество вычислений примерно пропорционально некоторой функции от n. Если количество вычислений равно Kn2 для любой константы K, мы говорим, что количество вычислений равно O(n em>2) независимо от константы K. Поэтому совершенно неважно, что вы считаете примитивными операциями. Вы можете получить 9n2, кто-то, кто считает разные операции, может получить 7n2 или 3n2, но это не имеет значения — все равно O(n2). А члены более низкой степени (15n+6) вообще не учитываются, так как они растут медленнее, чем член Kn2 . Таким образом, они не имеют отношения к определению соответствующей формулы большого O.

person ajb    schedule 12.11.2014
comment
Значит ли это, что количество операций для внутреннего цикла for будет следующим: for (int j = 0; j ‹ i; ++j) (4(n(n-1)/2) Operations)< /i> сумма = сумма + массивX[j]; (5(n(n-1)/2) операций) - person Phillip; 13.11.2014
comment
@Phillip, я не уверен, так как я действительно не знаю, что вы считаете операцией. Боюсь, я не могу помочь вам здесь. Помните, что если тело цикла выполняется M раз, проверка j < i будет выполнена M+1 раз. - person ajb; 13.11.2014
comment
Итак, сам цикл будет запущен n(n-1)/2, и все будет внутри тела цикла, а затем к нему будут добавлены любые операции. Я не понимаю, откуда взялась часть /2? - person Phillip; 13.11.2014
comment
@Philip Поскольку внутренний цикл останавливается на j < i, это означает, что когда i=0 тело цикла выполняется 0 раз, когда i=1 - 1 раз, когда i=2 - 2 раза и так далее. Следовательно, общее количество его выполнения равно 0+1+2+...+(n-1) (поскольку n-1 является наибольшим значением i). Формула для этой суммы n(n-1)/2 — это просто алгебра. Найдите Арифметическую прогрессию, если вы не знаете, как выводится эта формула. - person ajb; 13.11.2014