Skip to content

Instantly share code, notes, and snippets.

@masiht

masiht/fibonacci.swift

Last active Aug 11, 2018
Embed
What would you like to do?
fibonacci algorithms in swift
// https://medium.com/swlh/fibonacci-swift-playground-f56d1ff3ea99
// recursive approach
// time: O(n^2)
// space: O(n^2)
func fib1(_ n: Int) -> Int {
guard n > 2 else { return n }
return fib(n-1) + fib(n-2)
}
////////////////////////////////////////////////
// Iterative approach
// time: O(n)
// space: O(n)
func fib2(_ n: Int) -> Int {
var fibs: [Int] = [0, 1]
(2...n).forEach { i in fibs.append(fibs[i - 1] + fibs[i - 2]) }
return fibs.last!
}
////////////////////////////////////////////////
// Iterative approach -- Space optimized
// time: O(n)
// space: O(1)
func fib3(_ n: Int) -> Int {
var a = 1
var b = 1
guard n > 1 else { return a }
(2...n).forEach { _ in (a, b) = (a + b, a) }
return a
}
////////////////////////////////////////////////
// Matrix approach
// time: O(n)
// space: O(1)
func fib4(_ n: Int) -> Int {
let M = [[1, 1], [1, 0]]
guard n > 2 else { return n }
var result: [[Int]] = M
(1..<n).forEach { _ in result = multiply(result, M) }
return result[0][0]
}
////////////////////////////////////////////////
// Matrix approach -- Optimized
// time: O(log n)
// space: O(log n)
func fib5(_ n: Int) -> Int {
var M = [[1, 1], [1, 0]]
guard n > 2 else { return n }
power(&M, n)
return M[0][0]
}
func power(_ matrix: inout [[Int]], _ n: Int) {
guard n > 1 else { return }
power(&matrix, n/2)
matrix = multiply(matrix, matrix)
if n % 2 != 0 {
let M = [[1, 1], [1, 0]]
multiply(matrix, M)
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment