I would like to improve my code style and its efficiency.
I'm just moving beyond the standard recursive approach to a lot of simple algorithms.
This post has two code snippets with slightly different but related problems. They're both in Python.
The first snippet is just to produce Fibonacci numbers. I think I've done this with O(n) time complexity. Do you have suggestions on how to make my code more readable and more efficient?
# Using bottom-up dynamic programming approach, define all fibonacci numbers def fib(num): # First and second generations are trivial if num == 1 or num == 2: return 1 # If not trivial, keep going: # Set up array allGenerations = [None] * (num + 1) allGenerations = 1 allGenerations = 1 # Fill in the array until you reach the given generation for i in range(3, num+1): allGenerations[i] = allGenerations[i - 1] + allGenerations[i - 2] return allGenerations[num]
The second snippet tries to use what I learned from the first snippet to solve a related problem. The numbers represent living rabbits. If rabbits lived forever, their population sizes would follow a fibonacci sequence. In this alteration, rabbits live for a fixed amount of time (input m). Newborn rabbits keep living, adult rabbits produce themselves and one offspring, and rabbits that are about to die just produce one offspring (see http://rosalind.info/problems/fibd/).
I'm not sure how to analyze the time complexity of this problem, but it seems high? So questions are (1) What is the time complexity of my solution? and (2) How can I improve efficiency and readability?
def rabbit(n, m): # First two generations are trivial if n == 1 or n == 2: return 1 # If not trivial, keep going: # Set up array allGenerations = [None] * (n + 1) # Each index in the generations will be another array whose indicies represent the ages of the rabbits in that generation allGenerations =  allGenerations = [0, 1] # Bottom-up filling of generations for i in range(3, n + 1): # Initalize answer as a list of number of rabbits at each age answer = [None] * (i) # Get the previous generation previous = allGenerations[i - 1] # Initalize the number of newborns newborns = 0 # From age 1 (first reproductive age) to either age at death # or the oldest in the previous generation (whichever comes first), produce newborn rabbits for j in range(1, min(m, len(previous))): newborns += previous[j] # The 0-index of the answer represents newborn rabbits answer = newborns # Move every element in the previous generation up one index into the new generation for k in range(0, len(previous)): answer[k + 1] = previous[k] # Put this answer into the list of all answers allGenerations[i] = answer # Return all living rabbits return sum(answer[:m]) # Some testcases import unittest class mainTest(unittest.TestCase): def test(self): self.assertEqual(rabbit(1, 3), 1) self.assertEqual(rabbit(2, 3), 1) self.assertEqual(rabbit(3, 3), 2) self.assertEqual(rabbit(4, 3), 2) self.assertEqual(rabbit(5, 3), 3) self.assertEqual(rabbit(6, 3), 4) self.assertEqual(rabbit(7, 3), 5) self.assertEqual(rabbit(25, 31), 75025) self.assertEqual(rabbit(30, 30), 832040) self.assertEqual(rabbit(35, 29), 9227437) self.assertEqual(rabbit(40, 28), 102333267) self.assertEqual(rabbit(45, 27), 1134880302) if __name__ == '__main__': unittest.main(argv=[''], exit = False)