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.

 Evolution:

 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.

  • 1
    $\begingroup$ Welcome to CS.SE! What's $M$? What's $N$? Shouldn't your running time depend on $k$, too? Do you care more about provable worst-case asymptotic running time, or about efficiency in practice? What context did you encounter this in -- is this an exercise, or are you trying to build a practical tool? Don't forget to give proper attribution to the source of this exercise! $\endgroup$ – D.W. Jun 30 '16 at 6:32
  • $\begingroup$ Well, actually M and N refers to the row number and col number of this array, I have fixed it, it is O(MNK) time complexity. What I really want is that if there's any possibility to lower my time complexity. Oh, btw, this is an example exercise, which you may address systematica.com/wp-content/uploads/… $\endgroup$ – Reyn S Jun 30 '16 at 10:08
  • $\begingroup$ Please edit the question to define what M, N, and K are. Why do you use K in one place and k in the other? Please edit to fix. Please edit to add full attribution to the question. Read the link I gave you for what we expect you to do: put quoted material in a quote block ("> "), list the name of the author (e.g., Systematica Investments) and site where you find it, and include a direct link to the place where you found it. Don't just leave clarifications in the comments; we want questions to be self-contained. $\endgroup$ – D.W. Jun 30 '16 at 17:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.