如何比较数组的大 O 时间复杂度与索引找到的值与数组切片

Question

我有以下数组，我只是想确保我在每个解决方案的时间复杂度方面是正确的运行

arr = [3,6,8,10,34]

# case one
result_one = [arr[-1], arr[-2], arr[-3]] 
# result = [34, 10, 8]

# case two
result_two = arr[-3:]
# result = [8, 10, 34]

基于case one在时间复杂度上常数O(1)，result_two切片方法是线性 O(n)，case_one 会比运行更快。这两种算法的假设和时间复杂度是否正确？

Answer 1

Big-O 运行时是关于 n 增加时的增长行为。在这种情况下，n 可以被视为 arr 的长度或提取的项目数：

就提取的项目数量而言，如果数量是可变的（不只是一个常数3），则两种解决方案都是O(n)。如果数字是常量，big-O是没有意义的；你做的工作量是固定的，不会改变，所以增长甚至不适用。
就arr的长度而言，以常量元素提取计数3，两种解决方案都是O(1)；除了长度为 0-2 arr 的微不足道的情况外，所有长度为 3 或更大的 arr 都需要相同的工作量来提取三个元素；将 arr 的大小加倍会使工作保持不变。

无论您怎么看，对于任何具有 O(1) 索引的序列类型，这两种解决方案在定义上都是相同的 big-O；在引擎盖下，切片必须完成与显式索引完全相同的工作，因此它们必须执行相同数量的工作。

在具有非O(1)项查找的序列类型上（例如，链表等，具有O(n)查找），切片优于big-O的重复索引就提取的项目数而言（因为它只需要找到切片的起点一次，而不是 n 次，使其成为 O(m+n) 其中 m 是链表的大小n 是要提取的项目数，它简化为 O(m) 因为您不能提取比现有更多的项目，而重复索引将是 O(m*n)，支付 O(m) 成本 n 次），但对于具有 O(1) 索引的简单 array-like 数据结构，两者将始终 big-O 等效，尽管切片可能会更快，因为它可以批量执行操作，而无需反复进出 Python 级别代码。对于短输入，它们的行为也会有所不同；如果输入少于三个元素，则静默切片 returns 短输出，而索引将死于 IndexError.

如何比较数组的大 O 时间复杂度与索引找到的值与数组切片

how to compare big O time complexity of an array with values found by indexes versus array slicing

python

arrays

python-3.x

algorithm

data-structures