TLE 问题 - Python 中的 .index() 方法是否慢？

Question

如果我有点新手，请原谅我，几周前我开始自学如何编码。

我一直在解决 cses.fi 中的问题集。我遇到了“收集数字”问题，它本质上是在问我们：给定一个数组，例如 [4, 2, 1, 5, 3]，我们必须“收集”多少次数字才能使数字井井有条从 1 到 n 递增。

在这种特殊情况下，我们需要 3 轮，因为我们迭代一次并收集“1”，第二次迭代给我们“2, 3”，最后第三次迭代给我们“4, 5”。

我在 Python 编程并最终找到了解决方案，尽管我在提交时遇到了 TLE 错误。我做了一些调整，发现 .method() 大大降低了我的代码速度。

TLE 代码：

n = int(input())
arr = list(map(int, input().split()))
i_arr = [0] * (n + 1)
res = 1
 
for i in arr:
    i_arr[i] = arr.index(i)
for i in range(1, len(i_arr)):
    if i_arr[i] < i_arr[i - 1]:
        res += 1
 
print(res)

0.09 秒的接受代码运行时间：

n = int(input())
arr = list(map(int, input().split()))
i_arr = [0] * (n + 1)
for i in range(n):
    i_arr[arr[i]] = i
res = 1
for i in range(1, len(i_arr)):
    if i_arr[i] < i_arr[i - 1]:
        res += 1
 
print(res)

这两个代码块之间的唯一区别在于我在第一个 for 循环中建立索引的方式。

我的问题是：python 中的 ,index 方法是否慢？如果是，为什么？感谢您的帮助。

Answer 1

是的，它会慢很多，尤其是随着 'n' 的大小增长。

在 TLE 代码中，您的意思是：

通过在数组中搜索 'i' 找到 'i' 的索引。请记住，python 程序不能假定列表是有序的或任何东西，因此它必须手动搜索第一次出现的 'i'
当 'n' 较小时这很好，因为例如在第一次迭代期间，.index() 将首先快速查找 i=0 和 return，因为列表中的第一个数字恰好是 0.
但是想想随着 n 的增长，你基本上是在要求 .index() 每次遍历列表 +1 个位置
这个 for-loop 就是所谓的 O(n^2) 算法，因为对于 'n' 中的每个 'i'，最坏的情况是搜索 n 项以找到return 的索引。最坏的情况发生在 for-loop.

您的第二个实现不需要像第一个实现那样遍历列表 n-times。

当然，正如我提到的，第一个实现不必每次都遍历整个列表，但随着循环的进行和 'i' 的增长，情况会变得更糟。

TLE 问题 - Python 中的 .index() 方法是否慢？

TLE issue - is .index() method slow in Python?

python

algorithm

indexing