为什么在数组中获取值的成本是O(1)

简单的答案

按索引查找数组中的值是O(1)。

在中搜索值 未排序的数组 为O(n)。

Big O notation

数组是计算机编程中的一种抽象数据结构。在讨论抽象数据结构的大O表示法时,我们要问的是:在给定任意数量的元素的情况下,将算法应用于抽象数据结构需要多长时间。换句话说:作为抽象结构中数据的函数,您的算法有多快。

Swift上下文

这不是 Machine Code 。Swift是 high-level programming language 。这意味着Swift代码本身就是对其运行的计算机内部细节的抽象。因此,当我们在Swift中讨论数组的大O表示法时,我们并没有真正讨论它是如何存储在内存中的,因为我们假设它存储在内存中的方式是 Array data structure 。我认为理解这一点很重要,这也是为什么 Ruby 将比中的阵列慢 C 例如,因为一种语言是其运行的计算机的更大抽象。我们现在可以向前看了,知道在Swift数组的上下文中关于Big O的讨论确实受到其在计算机中的底层实现的影响,但在使用Big O时,我们仍然指的是实例化数组的完美版本。

在未排序的数组中搜索值为O(n)

|2 | 6 | 10 | 0|

上面的文字是包含4个元素的数组的视觉表示。
如果我说每次你看一个元素,那就是一个复杂度为1的动作。
然后我说,我想让你从左到右只看一次每个元素。复杂性是什么?
4、好。

停下。

|2 | 6 | 10 | 0|

Swift中为:

let array: Array<Int> = [2, 6, 10, 0]

我想让你从左到右只看一次每个元素。

我是一个写Swift的电脑程序员,而你就是电脑。

for element in array {
    print(element)
}

让我们把它变得更一般。假设我们不知道数组中有什么,我们给它起了个名字怎么样 book 。我现在问:我想让你从左到右只看一次每个元素。复杂性是什么?
好吧,这是书中元素的数量!好的
OK Computer 。从左到右看这本书的每一页,直到这一页上有一个感叹号为止。如果你找到了,给我看看它所在的页面,如果你没有找到,告诉我你没有找到。复杂性是什么? 由于您和我都不知道哪一页(如果有的话)包含感叹号,因此完全有可能最后一页是唯一包含感叹号的页。也可能所有页面都不包含感叹号。

我们书的页数是n 。

在最坏的情况下,无论我们是否找到感叹号,我们都必须至少看一次书中的每一页,直到找到包含!

O(n)

在一个示例中综合所有内容

struct Page {
    let content: String
    func contains(_ character: Character) -> Bool {
        return content.contains(character)
    }
    init(_ content: String) {
        self.content = content
    }
}

typealias Book = Array<Page>

let emotionalBook: Book = [Page("this"),
                           Page("is"),
                           Page("a"),
                           Page("simple"),
                           Page("book!")]

let unemotionalBook: Book = [Page("this"),
                             Page("book"),
                             Page("lacks"),
                             Page("emotion.")]

enum EmotionalBook: Error {
    case lacking
}

func findExclamationPoint(within book: Book) throws -> Page {
    //Look at every single page once.
    for page in book {
        if page.contains("!") {
            return page
        }
    }
    //Didn't find a page with ! inside it
    throw EmotionalBook.lacking
}

do {
    //Discovers the last page!
    let emotionalPage = try findExclamationPoint(within: emotionalBook)
    print(emotionalPage.content)
} catch {
    print("This book is \(error) in emotion!")
}

do {
    //Doesn't discover a page, but still checks all of them!
    let emotionalPage = try findExclamationPoint(within: unemotionalBook)
    print(emotionalPage.content)
} catch {
    print("This book is \(error) in emotion!")
}

我希望这有帮助!

这是我能找到的最好的答案 stackoverflow it自身

一 array 从特定的 memory 住址 start 。元素占用一定数量的字节 element_size 。这个 大堆 元素依次位于 记忆力 从 开始 地址位于。因此可以计算元素的内存地址 i 具有 start + i * element_size 。此计算与阵列大小无关,因此 O(1) 。 原始答案在这里 click me