Advertisement
Guest User

Untitled

a guest
Oct 25th, 2016
124
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.37 KB | None | 0 0
  1. A simple solution (horribly inefficient):
  2. function fib(n) {
  3. if (n <= 1) return 1;
  4. return fib(n - 1) + fib(n - 2);
  5. }
  6.  
  7. function fibArray(n) {
  8. let arr = [];
  9. for (let x=0; x<n; x++) {
  10. arr.push(fib(x));
  11. }
  12. return arr;
  13. }
  14.  
  15. Time Complexity: O(n*2^n)
  16. Space Complexity: O(n)
  17. So, how do we improve? Memoize the recursive function so we don't keep recomputing the same values:
  18.  
  19. function fibArray(n) {
  20.  
  21. let fibMemo = new Map();
  22.  
  23. function fib(n) {
  24. if (fibMemo.has(n)) return fibMemo.get(n);
  25. if (n <= 1) return 1;
  26. const result = fib(n - 1) + fib(n - 2);
  27. fibMemo.set(n, result);
  28. return result;
  29. }
  30.  
  31. let arr = [];
  32. for (let x=0; x<n; x++) {
  33. arr.push(fib(x));
  34. }
  35. return arr;
  36. }
  37.  
  38. Time Complexity: O(n)
  39. Space Complexity: O(n)
  40. Not bad, but the memoization is really overkill. We could write this cleaner by using the previous values as we build the array:
  41.  
  42. function fibArray(n) {
  43. let arr = [];
  44. for (let x=0; x<n; x++) {
  45. arr.push(
  46. x < 2 ? 1 : arr[x - 1] + arr[x - 2]
  47. );
  48. }
  49. return arr;
  50. }
  51.  
  52.  
  53. Things to keep in mind:
  54. ? Follow instructions:
  55. ? Does your code always return an array?
  56. ? Is it always of length n?
  57. ? Know the time and space complexity of the code you write
  58. ? Handle edge cases. What if n is zero?
  59. ? Test your code! Walk through a sample input
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement