Big-O Обозначение функции

Question

Следующая функция принимает одномерный массив A размера n в качестве параметра и возвращает двумерный массив M размера nx n. М хранит средние значения. Эти средние значения вычисляются из массива A между 2 итерационными переменными (i a j), если i <= j, с использованием формулы M [i] [j] = (A [i] + ... + A [j]) / ( J-I + 1). Например, если i = 1, а j = 3. Тогда M [0] [3] сохранит значение, рассчитанное из M [1] [3] = (A [1] + A [2] + A [3]) / 3-1 + 1 </p>

 public float[][] averageArray(float[] A){
        int n = A.length;
        float sum;
        float[][] M = new float[n][n];

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

                if(i<=j) {
                    sum = 0;
                    for (int k = i; k <= j; k++) {
                        sum += A[k];

                    }
                    M[i][j] = sum / (j - i + 1);
                }else{
                    M[i][j] = 0;
                }

                System.out.println("["+ i +"]" + "["+ j +"]: "+ M[i][j]);
            }

        }
        return M;
    }

Я запутался в обозначении этой функции. Я знаю, что первые два цикла for выдают большой O из O (n ^ 2), но поскольку третий l oop является условным, я не уверен, как поместить это в нотацию big-O. Из тестов я обнаружил, что число выполненных 3-х l oop увеличивается со значением j (например, если j = 3, то l oop выполняется 3 раза, если j = 5, тогда l oop будет выполняться 5 раз).

Answer 1

tl; dr , если вы не уверены, как он учитывает время выполнения big-o, создайте суммирование для l oop, а затем выполните преобразование это суммирование в функцию n

Иногда вы будете сталкиваться с такими вопросами, как «сколько раз строка внутри самой внутренней l oop выполнялась в терминах n Это не совсем анализ времени выполнения, но, тем не менее, это анализ. Он поможет вам получить более полное представление о времени выполнения big-o.

Может быть полезно поместить счетчик во внутренний l oop и посмотрите, сколько раз он выполняется.

Также может быть полезно нарисовать сетку и раскрасить квадраты, где i <= j и j - индекс строки (так как это первый l oop ' переменная s), а i - индекс столбца). Когда вы это сделаете, вы увидите, что все цветные квадраты разбивают квадратную сетку на 2 треугольника по диагонали от верхнего левого до нижнего правого. линия все еще имеет значение (потому что ты сказал <=, а не <). Цветные квадраты будут нижним / левым треугольником.

Это просто изображение того, где самый внутренний l oop действительно что-то сделает .

Внешние 2 цикла теперь будут повторяться по каждому месту в сетке. Мы назовем это текущее местоположение . Строка кода во внутреннем l oop теперь будет выполняться один раз для каждого цветного квадрата выше текущего местоположения в этом столбце сетки (и один раз для текущего местоположения , если это каждый раз новое местоположение определяется внешними 2 петлями.

После визуализации вы можете легче увидеть, сколько раз это будет выполнено. Первый столбец сетки имеет n цветных квадратов. При первом подсчете этого столбца будет выбран верхний левый квадрат (j = 0, i = 0). Второй раз будет, когда (j = 1, i = 0). Итак, давайте заполним сетку, где значение в каждом месте - это число раз, которое подсчитывается каждая ячейка. Это будет так:

[n,  0 ,  0,  0, ... ]
[n-1, n-1, 0, 0, ... ]
[n-2, n-2, n-2, 0, ...]

Теперь вы можете видеть картинку. Суммируя все в , эта сетка теперь скажет вам, сколько раз ваш самый внутренний l oop был выполнен.

1. В первом ряду 1 n
2. Во втором ряду 2 (n-1) '
3. Третий строка имеет 3 (n-2) * s

Вы можете увидеть шаблон (nj) * (j + 1) как сумму для каждой строки.

Суммируйте по строкам, чтобы получить сумму.

В итоге вы получите такую ​​сумму:

for(int i = 0; i < n; i++)
    sum += (n-i)*(i+1);
return sum;

Это только для количества раз, которое внутренний большинство л oop выполнено. Теперь для времен исполняется самый внутренний l oop 1070 * not . Эта часть намного проще. Это просто количество неокрашенных квадратов в сетке из предыдущих.

Поскольку это сетка n на n , n ² / 2 может показаться правильным ответом. НО основные диагональные квадраты все цветные. n ² / 2 уже считает половину этой строки, поэтому мы должны удалить другую половину: n / 2.

Таким образом, общее количество выполнений будет равно for l oop сумма выше, плюс половина квадрата n (неокрашенные квадраты), минус половина n (потому что вы только что добавили половину диагонали, которая уже была окрашена в предыдущем плюс термин).

В конечном итоге это выглядит как

Значение первых двух слагаемых - это количество раз, которое делал самый внутренний для-l oop НЕ выполнить.

Когда я запускаю этот код, мои результаты следующие:

1. n = 10
   • inner-l oop выполнения: 220
   • Всего казней: 265
   • 220 + 10 ² / 2 - 10/2 (220 + 50 - 5 = 265)
2. n = 100
   • inner-l oop исполнений: 171700
   • всего исполнений: 176650
3. n = 1000
   • inner-l oop казни: 167167000
   • всего выполнений: 167666500
4. n = 10000
   • inner-l oop исполнений: 166716670000
   • всего исполнений: 166766665000
5. n = 100000
   • inner-l oop исполнений: 166671666700000
   • всего исполнений: 166676666650000
6. n = 100000000 (сделал это только для lolz, вы уже можете видеть шаблон)
   • inner-l oop исполнений: 166666671666666700000000
   • всего выполнений: 166666676666666650000000

И ДЛЯ МОЕГО ПОСЛЕДНЕГО РАСКРЫТИЯ, ПОЧЕМУ ВЫ ПРОЧИТАЛИ ЭТО ДАЛЬШЕ Это функция O (n ³ ).

Я не буду вдаваться в подробности, но сумма для количества выполнений самого внутреннего для -l oop упрощается до

Добавляя в 2 терминах, которые подсчитывают, сколько раз выполнялся самый внутренний l oop, который выполнял NOT , сгруппируйте подобные термины для более простого упрощения, и вы получите следующее:

Вы можете использовать эти последние 2 формулы для проверки данных, которыми я поделился выше. Вы также можете эмпирически проверить, добавив счетчики в свои циклы и запустив их, чтобы увидеть, сколько раз они выполняются, и сравнить их со значениями, приведенными в этих формулах (для значений, таких как предоставленные мною, вам нужно будет использовать BigInteger s). или какой-либо другой формат произвольно большого числа). Если вы не доверяете ни мне, ни своему компьютеру, вы также можете попробовать добавить эту информацию в онлайн-инструмент, который решает уравнения, такие как вольфрам альфа. Наконец, если это из экзаменационного вопроса, вы можете передать его своему профессору и продемонстрировать природу этой проблемы, и точное число for-loop выполнений, заданных n, равно длине массива A. Если все это не так, я, по крайней мере, показал, что это верно для степеней 10. Надеюсь, это поможет каким-то образом.

Answer 2

Обновление: На основании анализа @ loganrussell48 и комментария ниже, сделанный мной вывод о n^2 неверен.

---

Неправильный ответ:

Большие факторы, такие как n^2 'затмение', меньшие факторы, такие как тот, который вы ищете (который, как мы знаем, меньше n, поэтому ответ будет меньше n^3) .

Можно с уверенностью сказать, что ваш big-O больше n^2, но меньше n^3. Если вы посмотрите список временных сложностей (например, https://en.wikipedia.org/wiki/Time_complexity#Table_of_common_time_complexities), то увидите, что эти две сложности соседствуют.

Big-O - это все об упрощении. Постоянные факторы выпадают. Меньшие факторы выпадают. В этом случае третий коэффициент n (n * n * n) намного меньше, чем n. Условие выполняется половину времени и выполняется от i до j раз (оба меньше n, поэтому с использованием оценки половина от половины n). Этот третий коэффициент n теперь намного меньше, чем n.

Общие сложности, меньшие n, незначительны по сравнению с n^2.

В этом случае n^2 это важная вещь, которую вы пытаетесь передать.