基本算法概念、时间和空间复杂性：Swift 代码示例

terry 2年前 (2023-09-27) 阅读数 64 #数据结构与算法

算法概念

算法是解决特定问题的步骤的描述。它在计算机中表示为有界的指令序列，每条指令代表一个或多个操作。

摘自《大话数据结构》

简单地说，算法就是“问题的解决方案”。同一问题可以有多种不同的解决方案。尽管这些解决方案可以达到相同的结果，但运行每种算法所需的时间和空间资源可能有很大不同。

就花费的时间而言，让我们看看同一个问题的两种不同解决方案的效果会有多大差异：

现在让我们解决这个问题： 计算 1 到 100 之间的数字总和 。？代码中sumOpration1使用了循环遍历的方法； sumOpration2 使用公式对算术序列求和。

虽然两个函数都能得到正确的结果，但不难看出两个函数的性能存在差异：

遍历和求和所需的时间取决于传递给的n的大小和算术求和方法序列所需的时间完全与传输的n的大小无关。

如果遍历sum中n的输入值为100，则必须遍历100次并求和才能得到结果。那么如果n的传入值为一百万呢？

等差数列的求和函数中，无论n的值有多大，只需要一个公式即可求解。

从小处可见大处：世界上成千上万的问题（算法问题）都可以有相似的情况：同样的问题，同样的结果，但执行效率却截然不同。那么有没有一种方法可以衡量特定算法的性能，以方便人们选择，或者衡量算法之间的差异呢？答案是肯定的。

作者将呈现算法消耗的资源两个维度：时间复杂度和空间复杂度。

时间复杂度和空间复杂度

时间复杂度

算法的时间复杂度是指算法必须消耗的时间资源。一般来说，计算机算法是问题大小!n的函数f(n)，因此算法的时间复杂度写为：

常见的时间复杂度包括：常量阶O(1)、对数阶O( log n)、线性阶 O(n)、线性对数阶 O(nlog n)、二次阶 O(n^{2})、三次阶 O(n^{3})、!k 次方 O ( n^ {k})，指数阶 O(2^{n})}。随着问题规模n不断增大，上述时间复杂度不断增大，算法的执行效率变低。

比较几种复杂度：

从上图我们可以看出，二次阶O(n^{2})的复杂度随着n值的增加几乎呈线性增加；线性阶复杂度 O(n) 随着 n 的增加而线性增加；我们还看到，随着 n 的增加，常数阶 O(1) 的复杂度保持不变。

转向上一节的求和问题，我们可以看到遍历求和算法的复杂度是线性阶O(n)：随着求和最大值的大小线性增长；而算术序列的总和。该算法的复杂度为常数阶O(1)，其算法复杂度与输入值n的大小无关。

读者可以想象一个复杂度与输入值n的平方成正比的算法。

这里我举一个例子：查找数组中两个元素之和为某个值的元素索引的算法。矩阵为[0,2,1,3,6]，和为8：

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")
}

复制代码

上面的算法精确计算出两个元素的索引为1和4。由于两个级别的遍历，这里算法的复杂度是二次O(n^{2})。

其实不需要两层，只需要一层：在transition时我们知道当前元素的值a，只要其他元素中的值相同（target - a），即可以。因此，该算法的复杂度是线性阶 O(n)。

我们看一下代码实现：

//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})的算法在数据量很大的情况下是不可接受的。