Создание алгоритма с лучшим временем выполнения

У меня есть матрица A с номерами A [1], A [2] ..., A [n] и матрица B (nxn), которые я хочу сохранить все возможные суммы. Простой алгоритм, который вычисляет матрицу B является:Создание алгоритма с лучшим временем выполнения

for i=1,2,...,n 
    for j=i+1,i+2,...,n 
     add the number from A[i] to A[j] 
     save the results to B[i][j] 
    endfor 
endfor

Я хочу изменить этот алгоритм, чтобы быть лучше (чтобы лучше выполнения). Я изменил первый для i = 1,2, ... n до i = 1 и i увеличил это в конце второго. Я также считаю, что я сделал больше вычислений, которые необходимы. Чтобы вычислить B [1] [5], я должен вычислить A [1] [2] + A [1] [3] + A [1] [4], но эта сумма также находится в B [1] [4]. Поэтому я могу вычислить это с меньшим вычислением (B [1] [4] + A [1] [5]). Может ли кто-нибудь помочь мне улучшить этот алгоритм?

источник

2016-03-23 Lee Yaan

Является ли «А» вектором или матрицей? Можете ли вы записать на простом английском языке или уравнение, что такое определение 'B [i] [j]'? – biziclop

Ваше второе решение эффективно и просто, поскольку оно получается, это всего лишь небольшое количество арифметических операций для каждого значения, необходимого для вывода. Он работает в O (n^2), который является размером вывода, вы не будете лучше, чем с точки зрения асимптотической сложности. – amit

B [1] [5] не содержит A [1] [2] + A [1] [3] + A [1] [4]. Он содержит A [1] [4] + A [1] [5]. Трудно показать это в комментарии. Вот небольшой скрипт R для первой строки с выходом: [code] local ({A = 1: 5; B = rep (NA, 4), для (j в 2: 5) {B [j] = A [ j-1] + A [j]}; rbind (A = A, B = B)}) [/ code] [код] A 1 2 3 4 5 [/ code] [code] B NA 3 5 7 9 [ /код] – DAV

for i=1,2,...,n 
    for j=i,i+1,i+2,...,n 
     if i == j then B[i][j] = A[j] 
     else B[i][j] = B[i][j - 1] + A[j] 
    endfor 
endfor

источник

2016-03-23 12:03:49 Sorin

Создание алгоритма с лучшим временем выполнения

ответ

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