Сложность алгоритма обхода трехмерного массива - PullRequest
Новая
       20

Сложность алгоритма обхода трехмерного массива

1 голос
/ 30 апреля 2019

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

def process_matrix(k: int, V: int):
    import numpy as np
    sp_matrix = np.zeros((V, V, k))

    for e in range(k):
        for i in range(V):
            # Note that the range of index j decreases while index i is growing 
            for j in range(i, V):
                # Also the index a decreases acording to index i
                for a in range(i, V):

                    if (something):
                        sp_matrix[i][j][e] = set_some_value()

Как видите, я не рассматриваю значения j V * (1 + V) / 2 * k

k -> самый внешний цикл

V * (1 + V) / 2 -> для второго и третьего цикла Я использовал формулу Гаусса для добавления последовательных чисел

В некотором приближении сложность этих трех циклов, я думаю, составляет O (((V ^ 2) / 2) * k) .

Сначала я подумал, что внутренний цикл вносит вклад в O с другим (1 + V) / 2. С результатом (V * (1 + V) / 2 * k) * (1 + V) / 2. Но потом я рассмотрел эту ситуацию:
k = 1
V = 3
Полученный массив: 


        <sup>j=0</sup>  <sup>j=1</sup>  <sup>j=2</sup>
    <sup>i=0</sup> | 3 | 3 | 3 |       
    <sup>i=1</sup> | x | 2 | 2 | 
    <sup>i=2</sup> | x | x | 1 |
    (the values in the matrix rapresents how many times the most inner loop.. loops)

Всего: 3 + 3 + 3 + 2 + 2 + 1 = 14
Я ожидаю того же значения, используя мою формулу (V * (1 + V) / 2 * k) * (1 + V) / 2,
(3 * (1 + 3) / 2 * 1) * (1 + 3) / 2 = 12
Но это не так ...

1 Ответ

0 голосов
/ 30 апреля 2019

Big-O нотация о настройке верхних пределов, игнорируя постоянные факторы. В этом смысле, учитывая 3 внешних цикла, O(((V^2)/2)*k) = O(k * V^2), а если k - постоянная, = O(V^2).

Однако, если вы начнете считать выполнения самого внутреннего кода и сравнивать их с ожидаемым числом выполнений, вы покидаете территорию big-O, поскольку постоянные факторы больше нельзя игнорировать. Кроме того, подсчет выполнений одной инструкции, хотя и полезен, ни в коем случае не является столь же точным, как измерение реальной производительности (которая, однако, будет зависеть от конкретной рабочей нагрузки и машины / среды, на которой вы ее тестируете).

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

let K=1, V=6, t=0;  // t is for counting totals; reset to 0 for each try
for (let k=0; k<K; k++)               // inside repeats K times
    for (let i=0; i<V; i++)           // inside repeats V*K times
        for (let j=i; j<V; j++)       // inside repeats (V+1)*(V) / 2 * K times
            for (let a=i; a<V; a++)   // inside repeats (V+1)*(V+.5)* V / 3 * K times
                console.log(k,i,j,a,++t, (V+1)*(V+.5)* V / 3 * K);
...