Как я могу сделать этот алгоритм более эффективным?

У меня есть Алгоритм, который создает 2D-массив, содержащий сумму всех возможных значений. Например, для массива [1,5,8,4,5] 2D-массив sums[1][3] должен возвращать сумму индекса 1-3 в исходном массиве (17). Я считаю, что с точки зрения большого О, эффективность равна O (N). Есть ли способ сделать этот алгоритм более эффективным?Как я могу сделать этот алгоритм более эффективным?

public static int[][] sum(int[] values){ 
    int[][] sums = new int[values.length][values.length]; 
    for(int x = 0; x < values.length; x++){ 
     int total = 0; 
     for(int y = x; y < values.length; y++) { 
      total += values[y]; 
      sums[x][y] = total; 
     } 
    } 
    return sums; 
}

источник

2016-11-10 Top Cat

Вам нужно заполнить таблицу размером 'N^2'. Как в мире вы можете сделать это меньше, чем 'O (N^2)' ?? –

Подобный вопрос. может выполняться в O (nlog (n)). http://stackoverflow.com/a/37907843/3160529 – Shubham

Это именно то, что мне было интересно. Это вопрос в моих лекционных слайдах, и я пытался это понять. –

Вы можете решить эту проблему в O(n) времени и пространстве с массивом префиксом суммой:

array = [1, 5, 8, 4, 5] 
prefixes = [1, 6,14,18,23] 

sums(1,3) = prefixes[3] - prefixes[0] = 18 - 1 = 17

источник

2016-11-10 19:53:53

Это ни в коем случае не отвечает на вопрос. 'sums (1, 3) = array [1] + array [3]'. Так в чем смысл? Вы заменили сложение на вычитание. И он не заполняет 2D-массив. –

@EugeneSh. Спасибо за ваш комментарий. Разве 'array [1] + array [3]' равно '9'? Я думаю, что OP означал 'sums [1] [3]' должен возвращать сумму для 'array [1] + array [2] + array [3]', что было бы '5 + 8 + 4 = 17'. Насколько я понимаю, вопрос: «Как я могу сделать этот алгоритм более эффективным?» и я думаю, что мой ответ предлагает один из способов сделать это. –

Ваш ответ работает, однако это не то, что мне нужно. Я ищу для алгоритма, который создает массив 2, так что 'arr [1] [3]' будет возвращать сумму всех значений из индекса 1-3. В этом ответе используется метод вычисления суммы (хотя это, скорее всего, невозможно). –

Вычислить prefix сумму следующим образом:

public static int[] sum(int[] values){ 
    int[] prefix_sums = new int[values.length]; 
    prefix_sums[0] = values[0]; 
    for(int x = 1; x < values.length; x++){ 
     prefix_sums[x] = prefix_sums[x-1] + values[x]; 
    } 
    return prefix_sums; 
}

По Вашему запросу, вы хотите найти сумму из индекса x для индекса y (индексирование на основе индекса), вот как получить сумму:

if(x==0) 
    result = prefix_sums[y]; 
else 
    result = prefix_sums[y] - prefix_sums[x-1];

Надеюсь, что это поможет !!!

источник

2016-11-11 05:25:30

Как я могу сделать этот алгоритм более эффективным?

ответ

Смежные вопросы