Created
April 28, 2015 05:19
-
-
Save connorjclark/db62c9aa7be2e049a472 to your computer and use it in GitHub Desktop.
algorithms
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
def time_it(&block) | |
before = Time.now | |
block.call() | |
Time.now - before | |
end | |
def display_time(&block) | |
puts "time took: #{time_it(&block)} seconds" | |
end | |
# linear time - O(n) | |
display_time { | |
n = 1000000 | |
sum = 0 | |
n.times { |i| | |
sum += i | |
} | |
puts sum | |
} | |
# constant time - O(1) | |
display_time { | |
n = 1000000 | |
puts n * (n - 1) / 2 | |
} | |
# O(n^2) | |
# O(log n) | |
# O(1) | |
display_time { | |
# O(n) | |
n = 10000000 | |
@numbers = n.times.map { rand(100) } | |
} | |
def binary_search(array, value) | |
return false if array.empty? | |
middle_index = array.length/2 | |
middle_value = array[middle_index] | |
if middle_value == value | |
true | |
elsif middle_value > value | |
binary_search(array[0...middle_index], value) | |
else | |
binary_search(array[(middle_index+1)..-1], value) | |
end | |
end | |
# worst case | |
# value is not in the array... | |
# how long will this algorithim take? | |
# array.length = 1024 | |
# 1) 1024 | |
# 2) 512 | |
# 3) 256 | |
# 4) 128 | |
# 5) 64 | |
# 6) 32 | |
# 7) 16 | |
# 8) 8 | |
# 9) 4 | |
# 10) 2 | |
# 11) 1 | |
# 12) 0 | |
# => false | |
display_time { | |
# O(log2 n) | |
puts binary_search(@numbers, 20000) | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment