How can I reduce time complexity on this algorithm?-CodePudding

I have this exercise and the goal is to solve it with complexity less than O(n^2).

You have an array with length N filled with event probabilities. Create another array in which for each element i calculate the probability of all event to happen until the position i.

I have coded this O(n^2) solution. Any ideas how to improve it?

probabilityTable = [0.1, 0.54, 0.34, 0.11, 0.55, 0.75, 0.01, 0.06, 0.96]

finalTable = list()

for i in range(len(probabilityTable)):
    finalTable.append(1)
    for j in range(i):
        finalTable[i] *= probabilityTable[j]

for item in finalTable:
    print(item)

CodePudding user response：

probabilityTable = [0.1, 0.54, 0.34, 0.11, 0.55, 0.75, 0.01, 0.06, 0.96]

finalTable = probabilityTable.copy()

for i in range(1, len(probabilityTable)):
    finalTable[i] = finalTable[i] * finalTable[i - 1]

for item in finalTable:
    print(item)

CodePudding user response：

new_probs = [probabilityTable[0]]
for prob in probabilityTable[1:]:
    new_probs.append(new_probs[-1]   prob)