ios - Swift的 map 和过滤器功能时间复杂度

我已经使用Swift 4以两种不同的方式实现了numJewelsInStones函数。

我想比较每个实现的时间和空间复杂度。但是，我在一个实现中使用某些本地方法，例如filtering a string，然后在另一个实现中使用mapping a string to an array of single characters。我想知道这些 native 函数的时间复杂度。另外，如果我使用字符串范围来获取字符串中每个字符的出现，该怎么办。我想了解这些原生函数(特别是Swift)如何影响整个BigO。

实现1:
过滤一个字符串(如果我忽略过滤器函数，可以使用for循环，我会说Big O是O(n)，对吗？)

//J - represents types of stones that are jewels
//S - represents the stones I have
func numJewelsInStones(_ J: String, _ S: String) -> Int {
    var sum = 0 //Sum - represents how many of the stones I have are also jewels
    for jewel in J {
        sum = sum + S.filter {$0 == jewel}.count //add sum of occurrences for each stone that is a jewel
    }
    return sum
}
print(numJewelsInStones("aA", "aAAbbbb")) //prints 3
print(numJewelsInStones("z", "ZZ"))       //prints 0

实现2:
我要做的第一件事是将字符串映射到单个字符的数组，否则我将在counts[stone] = (counts[stone] ?? 0) + 1行上收到错误“无法将字符串类型为[String:Int]的值与字符类型的索引进行子字符串化”
UPDATE:仅指出我意识到，如果我只是将counts字典的定义更改为var counts: [Character: Int] = [:]，就可以避免上述错误，我什至不需要将字符串映射到字符数组。哎呀。不过，出于问题考虑，我将其保留为原样。

func numJewelsInStones2(_ J: String, _ S: String) -> Int {
        let jewels = J.map { String($0) }
        let stones = S.map { String($0) }
        var counts: [String: Int] = [:]
        var sum = 0
    for stone in stones {
        counts[stone] = (counts[stone] ?? 0) + 1 //frequency count dict
    }
    for jewel in jewels { //for every jewel
        if let count = counts[jewel]  { //if the jewel exists in the frequency count dict
            sum = sum + count //add its count to the total sum
        }
    }
    return sum
}

print(numJewelsInStones2("aA", "aAAbbbb")) //prints 3
print(numJewelsInStones2("z", "ZZ"))       //prints 0

最佳答案

Swift标准库中的所有高阶函数(例如map，flatMap/compactMap，filter和reduce)通常都具有O(n)时间复杂性，因为它们全部都在完整的集合中工作，它们被调用，并且它们访问每个元素仅一次，因此它们具有线性时间复杂度。

考虑到这一点，您的第一个实现具有O(J*S)时间复杂度，因为对于J中的每个元素，您都使用S遍历了filter的所有元素。

另一方面，您的第二个实现具有大致线性的时间复杂度，具体取决于哪个String中包含更多Character或S或J，其时间复杂度为O(J)或O(S)，因为您没有任何嵌套循环，因此只能迭代J和S顺序。

实现1或2是否更有效完全取决于J和S的大小。

关于ios - Swift的 map 和过滤器功能时间复杂度，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/49887447/