<commit_before>http://en.wikipedia.org/wiki/Fibonacci_number

Fibonacci Number or Fibonacci Sequence:

F1 = F2 = 1
Fn = Fn-1 + Fn-2

Compute Fn

====================================
====================================
====================================

1. Naive Recursive Algorithm (Exponential cost)

T(n) = T(n-1) + T(n-2) + θ(1)

Where θ(1) = Constant time (loading, returning, addition, ... etc.)

def fib(n):
    """
    Returns the next Fibonacci sequence for a given `n`.
    """
    if n <= 2:
        f = 1
    else:
        f = fib(n - 1) + fib(n - 2)
    return f

Smart algorithm? Nope
 -- Many nodes are computed over again
 -- Exponential cost in time (non-memorized)
 -- No direct space cost as it's non-memorized
 -- Has recursion cost (time + space)

                  Fn
                  /\
                 /  \
              Fn-1   \
              / \     \
           Fn-2 Fn-3  Fn-2
                       /\
                      /  \
                    Fn-3 Fn-4

Note: Fn-x nodes are all recalculated when x > 1. Very expensive.

File: naive_recursive_algorithm.py
run:  python recursive_algorithm_naive.py

====================================
====================================
====================================


2. Memorized Recursive Algorithm (Linear cost)

T(n) = F(1), F(2), ... F(n)
T(n) = θ(n) # constant time to calculate each node


memorized = {}
def fib(n):
    """
    Returns the next Fibonacci sequence for a given `n`.
    """
    if n in memorized:
        return memorized[n]

    if n <= 2:
        f = 1
    else:
        f = fib(n - 1) + fib(n - 2)

    memorized[n] = f
    return f


Good algorithm? Better
-- All nodes are ONLY computed once
-- Linear cost in time (memorized)
-- Linear space cost  of memorization
-- Nodes are calculated once and remembered.
-- Has recursion cost (time + space)

                  Fn
                  /\
                 /  \
              Fn-1   \
              / \     \
           Fn-2 Fn-3  Fn-2    # load from memory @ θ(1)
                       /\
                      /  \
                    Fn-3 Fn-4 # load from memory @ θ(1)


File: recursive_algorithm_memorization.py
run:  python recursive_algorithm_memorization.py

====================================
====================================
====================================


3. Memorized Iterative Algorithm (Linear cost)

T(n) = ... F(n-3) -> F(n-2) -> F(n-1) -> F(n)
Subproblem dependency - Bottom up Dynamic Programming Algorithm
Saves space (memorization) as we only need the last two values since
we are moving bottom up.

memorized = {}
def fib(n):
    """
    Returns the next Fibonacci sequence for a given `n`.
    """
    for k in range(1, n+1):
        if k <= 2:
            f = 1
        else:
            f = memorized[k - 1] + memorized[k - 2]
        memorized[k] = f
    return memorized[n]


Good algorithm? Even Better
-- All nodes are ONLY computed once
-- Linear cost in time (memorized)
-- Constant space cost of memorization (last two calculations needs saving)
-- No recursion cost (time + space)


  bottom-up       Fn
    ^^^           /\
     |           /  \
     |        Fn-1   \
     |        / \     \
     |    Fn-2 Fn-3  Fn-2
                       /\
                      /  \
                    Fn-3 Fn-4


File: iterative_algorithm.py.py
run:  python iterative_algorithm.py.py





<commit_msg>update text file<commit_after>http://en.wikipedia.org/wiki/Fibonacci_number

Fibonacci Number or Fibonacci Sequence:

F1 = F2 = 1
Fn = Fn-1 + Fn-2

Compute Fn

====================================
====================================
====================================

1. Naive Recursive Algorithm (Exponential cost)

T(n) = T(n-1) + T(n-2) + θ(1)

Where θ(1) = Constant time (loading, returning, addition, ... etc.)

def fib(n):
    """
    Returns the next Fibonacci sequence for a given `n`.
    """
    if n <= 2:
        f = 1
    else:
        f = fib(n - 1) + fib(n - 2)
    return f

Smart algorithm? Nope
 -- Many nodes are computed over again
 -- Exponential cost in time (non-memorized)
 -- No direct space cost as it's non-memorized
 -- Has recursion cost (time + space)

                  Fn
                  /\
                 /  \
              Fn-1   \
              / \     \
           Fn-2 Fn-3  Fn-2
                       /\
                      /  \
                    Fn-3 Fn-4

Note: Fn-x nodes are all recalculated when x > 1. Very expensive.

File: recursive_algorithm_naive.py
run:  python recursive_algorithm_naive.py

====================================
====================================
====================================


2. Memorized Recursive Algorithm (Linear cost)

T(n) = F(1), F(2), ... F(n)
T(n) = θ(n) # constant time to calculate each node


memorized = {}
def fib(n):
    """
    Returns the next Fibonacci sequence for a given `n`.
    """
    if n in memorized:
        return memorized[n]

    if n <= 2:
        f = 1
    else:
        f = fib(n - 1) + fib(n - 2)

    memorized[n] = f
    return f


Good algorithm? Better
-- All nodes are ONLY computed once
-- Linear cost in time (memorized)
-- Linear space cost  of memorization
-- Nodes are calculated once and remembered.
-- Has recursion cost (time + space)

                  Fn
                  /\
                 /  \
              Fn-1   \
              / \     \
           Fn-2 Fn-3  Fn-2    # load from memory @ θ(1)
                       /\
                      /  \
                    Fn-3 Fn-4 # load from memory @ θ(1)


File: recursive_algorithm_memorization.py
run:  python recursive_algorithm_memorization.py

====================================
====================================
====================================


3. Memorized Iterative Algorithm (Linear cost)

T(n) = ... F(n-3) -> F(n-2) -> F(n-1) -> F(n)
Subproblem dependency - Bottom up Dynamic Programming Algorithm
Saves space (memorization) as we only need the last two values since
we are moving bottom up.

memorized = {}
def fib(n):
    """
    Returns the next Fibonacci sequence for a given `n`.
    """
    for k in range(1, n+1):
        if k <= 2:
            f = 1
        else:
            f = memorized[k - 1] + memorized[k - 2]
        memorized[k] = f
    return memorized[n]


Good algorithm? Even Better
-- All nodes are ONLY computed once
-- Linear cost in time (memorized)
-- Constant space cost of memorization (last two calculations needs saving)
-- No recursion cost (time + space)


  bottom-up       Fn
    ^^^           /\
     |           /  \
     |        Fn-1   \
     |        / \     \
     |    Fn-2 Fn-3  Fn-2
                       /\
                      /  \
                    Fn-3 Fn-4


File: iterative_algorithm.py
run:  python iterative_algorithm.py






{'fraction_non_alphanumeric': 0.19326371525224298, 'fraction_numerical': 0.015296367112810707, 'mean_word_length': 1.7059291683247115, 'pattern_counts': {'":': 0, '<': 9, '<?xml version=': 0, '>': 11, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '2063296', 'n_tokens_mistral': 2218, 'n_tokens_neox': 2002, 'n_words': 634}