# 大O

2021/04/13 19:56

Big-O表示符号

O(1) 常数级

O(log n)

O(n)

O(n log n)

O(n^2)

O(n^3) 三次方级

O(2^n)

O(n!)

O(1)

O(1)复杂性的最常见示例是访问数组索引。

​let value = array[5]​

O(log n)

var j = 1​

​while j < n {​

​   // do constant time stuff​

​   j *= 2​

​}​

O(n)

for i in stride(from: 0, to: n, by: 1) {​

​    print(array[i])​

​}​

O(n log n)

for i in stride(from: 0, to: n, by: 1) {​

​    var j = 1​

​    while j < n {​

​        j *= 2​

​        // do constant time stuff​

​}​

​}​

for i in stride(from: 0, to: n, by: 1) {​

​    func index(after i: Int) -> Int? {
// multiplies i by 2 until i >= n​
​        return i < n ? i * 2 : nil​

​}​

​    for j in sequence(first: 1, next: index(after:)) {​
​// do constant time stuff​

​    }​

​}​

O(n^2)

for i  in stride(from: 0, to: n, by: 1) {​

​     for j in stride(from: 1, to: n, by: 1) {​

​// do constant time stuff​

​    }​

​}​

O(n^3)

for i in stride(from: 0, to: n, by: 1) {​

​    for j in stride(from: 1, to: n, by: 1) {​

​        for k in stride(from: 1, to: n, by: 1) {​

​// do constant time stuff​

​}​

​    }​

​}​

O(2^n)

func solveHanoi(n: Int, from: String, to: String, spare: String) {​

​    guard n >= 1 else { return }​

​    if n > 1 {​

​         solveHanoi(n: n - 1, from: from, to: spare, spare: to)​

​    } else {​

​          solveHanoi(n: n - 1, from: spare, to: to, spare: from)​

​     }​

​}​

O(n!)​

​下面给出了O(n!)的最简单的例子。​​

func nFactFunc(n: Int) {​

​for i in stride(from: 0, to: n, by: 1) {​

​         nFactFunc(n: n - 1)​

​    }​

​}​

0 评论
0 收藏
0