I'm encountering a dynamic modelling problem. I've tried a lot of methods but it seems that all of them are of time complexity O(MNK), like the basic algorithm. I wonder if any guys can make some suggestions about any possible improvement of my time complexity?
A dynamic model is defined as follows:
State(n,m,t) is the state of the node (n,m) at time t. This value is either 0 or 1.
A neighbourhood of node (n,m) consists of 8 nodes around it. Denote LifeAround(n,m,t) as the number of nodes in the neighbourhood of (n,m) at time t that are in state 1.
If state(n,m,t)=0 (dead) then state(n,m,t+1)=1 (alive) iff LifeAround(n,m,t)=3
If state(n,m,t)=1 (alive) then state(n,m,t+1)=0 (dead) iff LifeAround(n,m,t)<2 or LifeAround(n,m,t)>3
a. Write a function that starts with the given state and develops the model through k steps on a fixed grid with zeros outside the boundary. b. Write a similar function that has no boundary.