Python
/
Collections
- 1 Language 9
-
Hello World
-
Variables
-
Functions
-
Conditional
-
Operators
-
While
-
Turtle
-
Script Mode
-
Debugging
- 2 Strings 6
-
Slice
-
Raw Strings
-
Regex
-
Validation
-
Config
-
Escape
- 3 Collections 5
-
Lists
-
Dictionaries
-
Efficiency
-
Tuples
-
References
- 4 Functions 5
-
Recursion
-
Factorial
-
Modulus
-
Reassignment
-
Approximate
- 5 Storage 8
-
Files
-
Databases
-
Pipes
-
With open
-
Shelve
-
Zip
-
Csv
-
Json
- 6 Class 4
-
Definition
-
Attributes
-
Functional
-
Methods
- 7 Goodies 5
-
Conditional Expression
-
List Comprehension
-
Generator
-
Named Tuple
-
Modules
- 8 Applications 5
-
Pythagora
-
Palindrome
-
Binary Search
-
Conway Game
-
Coin Flip
- 9 Scheduler 4
-
Time
-
Multithreading
-
Subprocess
-
Logging
- 10 Packages 2
-
Clipboard
-
Ocr
/
Efficiency
➟
➟
Last update: 18-11-2021
Slow
p197 In fibonacci function the bigger the argument, the longer the function runs.
# Slow (recursion)
#
# fb(0) = 0
# fb(1) = 1
# fb(n) = fb(n-1) + fb(n-2)
#
# The bigger the argument, the longer the function runs.
# It gets worst as the argument gets bigger.
loops = 0
def fibonacci(n):
global loops
loops = loops + 1
if n == 0: return 0
if n == 1: return 1
return fibonacci(n-1) + fibonacci(n-2)
assert fibonacci(4) == 3; print (loops) # 9
assert fibonacci(5) == 5; print (loops) # 24
assert fibonacci(6) == 8; print (loops) # 49
fibonacci(30)
print (loops) # 2692537 - Look Here
Fast
One solution is to keep track of values and store them in a dictionary.
# Fast (recursion & dictionary)
#
# fb(0) = 0
# fb(1) = 1
# fb(n) = fb(n-1) + fb(n-2)
#
# To make the algorith run faster ...
# one solution is to keep track of values and store them in a dictionary.
loops = 0
known = {0:0, 1:1}
def reset():
loops = 0
known = {0:0, 1:1}
def fibonacci(n):
global loops;
loops = loops + 1
if n in known:
return known[n]
res = fibonacci(n-1) + fibonacci(n-2)
known[n] = res
return res
reset(); assert fibonacci(4) == 3; print (loops) # 7
reset(); assert fibonacci(5) == 5; print (loops) # 10
reset(); assert fibonacci(6) == 8; print (loops) # 13
fibonacci(1000)
print (loops) # 2002 - Look Here
➥ Questions github Collections