算法基础概念、时间与空间复杂度：swift代码实例

算法的概念

算法是解决特定问题求解步骤的描述，在计算机中表现为指令的有限序列，并且每条指令表示一个或多个操作。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4502.html

摘自《大话数据结构》文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4502.html

简单说来，算法就是“一个问题的解法”。对于相同一个问题，可能会有多种不同的解法。这些解法虽然可以得到相同的结果，但是每个算法的执行所需要的时间和空间资源却可以是千差万别的。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4502.html

以消耗的时间的角度为出发点，我们看一下对于同一个问题，两种不同的解法的效率会相差多大：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4502.html

现在让我们解决这个问题：计算从1到100数字的总和。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4502.html

把比较容易想到的下面两种方法作为比较：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4502.html

1. 1到100循环遍历逐步相加
2. 等差数列求和

用Swift函数来分别实现一下：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4502.html

func sumOpration1(_ n:Int) -> Int{
    
    var sum = 0
    
    for i in 1 ... n {
        sum += i
    }
    
    return sum
}
sumOpration1(100)//5050



func sumOpration2(_ n:Int) -> Int{
    
    return (1 + n) * n/2
}
sumOpration2(100)//5050
复制代码

上面的代码中，sumOpration1使用的是循环遍历的方式；sumOpration2使用的是等差数列求和的公式。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4502.html

虽然两个函数都能得到正确的结果，但是不难看出两个函数实现的效率是有区别的:文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4502.html

遍历求和所需要的时间是依赖于传入函数的n的大小的，而等差数列求和的方法所需要的时间对传入的n的大小是完全不依赖的。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4502.html

在遍历求和中，如果传入的n值是100，则需要遍历100次并相加才能得到结果，那么如果传入的n值是一百万呢？文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4502.html

而在等差数列求和的函数中，无论n值有多大，只需要一个公式就可以解决。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4502.html

我们对此可以以小见大：世上千千万万种问题（算法题）可能也有类似的情况：相同的问题，相同的结果，但是执行效率缺差之千里。那么有没有什么方法可以度量某种算法的执行效率以方便人们去选择或是衡量算法之间的差异呢？ 答案是肯定的。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4502.html

下面笔者就向大家介绍算法所消耗资源的两个维度：时间复杂度和空间复杂度。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4502.html

时间复杂度与空间复杂度

时间复杂度

算法的时间复杂度是指算法需要消耗的时间资源。一般来说，计算机算法是问题规模!n的函数f(n)，算法的时间复杂度也因此记做：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4502.html

常见的时间复杂度有：常数阶O(1)，对数阶O(log n），线性阶 O(n)，线性对数阶O(nlog n)，平方阶O(n^{2})，立方阶O(n^{3})，!k次方阶O(n^{k})，指数阶 O(2^{n})}。随着问题规模n的不断增大，上述时间复杂度不断增大，算法的执行效率越低。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4502.html

拿其中几个复杂度做对比：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4502.html

从上图中我们可以看到，平方阶O(n^{2})随着n值的增大，其复杂度近乎直线飙升；而线性阶 O(n)随着n的增大，复杂度是线性增长的；我们还可以看到常数阶 O(1)随着n增大，其复杂度是不变的。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4502.html

参考上一节的求和问题，我们可以看出来遍历求和的算法复杂度是线性阶O(n)：随着求和的最大数值的大小而线性增长；而等差数列求和算法的复杂度为常数阶 O(1)其算法复杂度与输入n值的大小无关。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4502.html

读者可以试着想一个算法的复杂度与输入值n的平方成正比的算法。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4502.html

在这里笔者举一个例子：求一个数组中某两个元素和为某个值的元素index的算法。数组为[0,2,1,3,6]，和为8：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4502.html

func findTwoSum(_ array: [Int], target: Int) -> (Int, Int)? {
    
    guard array.count > 1 else {
        return nil
    }
    
    for i in 0..<array.count {
        
        let left = array[i]
        
        for j in (i + 1)..<array.count {
            let right = array[j]
            if left + right == target {
                return (i, j)
            }
        }
    }
    return nil
}

let array = [0,2,1,3,6]
if let indexes = findTwoSum(array, target: 8) {
    print(indexes) //1， 4
} else {
    print("No pairs are found")
}

复制代码

上面的算法准确地计算出了两个元素的index为1和4。因为使用了两层的遍历，所以这里算法的复杂度是平方阶O(n^{2})。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4502.html

而其实，不需要遍历两层，只需要遍历一层即可：在遍历的时候，我么知道当前元素的值a，那么只要其余元素里面有值等于（target - a）的值即可。所以这次算法的复杂度就是线性阶O(n)了。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4502.html

来看一下代码的实现：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4502.html

//O(n) 
func findTwoSumOptimized(_ array: [Int], target: Int) -> (Int, Int)? {
    
    guard array.count > 1 else {
        return nil
    }
    
    var diffs = Dictionary<Int, Int>()
    
    for i in 0..<array.count {
        
        let left = array[i]
        
        let right = target - left
        
        if let foundIndex = diffs[right] {
        
            return (i, foundIndex)
            
        } else {
            
            diffs[left] = i
        }
    }
    
    
    return nil
}
复制代码

同样地，上面两种算法虽然可以达到相同的效果，但是当n非常大的时候，二者的计算效率就会相差更大：n = 1000的时候，二者得到结果所需要的时间可能会差好几百倍。可以说平方阶O(n^{2})复杂度的算法在数据量很大的时候是无法让人接受的。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4502.html

空间复杂度

算法的空间复杂度是指算法需要消耗的空间资源。其计算和表示方法与时间复杂度类似，一般都用复杂度的渐近性来表示。同时间复杂度相比，空间复杂度的分析要简单得多。而且控件复杂度不属于本文讨论的重点，因此在这里不展开介绍了。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4502.html