时间戳

首页 > 解决方案 > O(n) 和 O(k) 是什么意思？

python - O(n) 和 O(k) 是什么意思？

问题描述

我有这个任务：

给定一个整数数组和一个数字 k，其中 1 <= k <= 数组的长度，计算每个长度为 k 的子数组的最大值。例如，给定数组 = [10, 5, 2, 7, 8, 7] 和 k = 3，我们应该得到： [10, 7, 8, 8]，因为：

10 = max(10, 5, 2)
7 = max(5, 2, 7)
8 = max(2, 7, 8)
8 = max(7, 8, 7)

在 O(n) 时间和 O(k) 空间中执行此操作。您可以就地修改输入数组，并且不需要存储结果。您可以在计算它们时简单地将它们打印出来。

O(n) 时间和 O(k) 空间是什么意思？

我得到了这个解决方案。这是否满足要求？如果不是，为什么不呢？

def foo(arr, k):
    for idx in range(0, len(arr) - k + 1):
        maxI = -1
        for i in arr[idx:idx + k]:
            if i > maxI:
                maxI = i

        print(maxI) #3; 3; 3; 5; 5; 5; 10; 22

arr = [0, 1, 3, 1, 2, 5, 5, 4, 10, 22]
k = 3

foo(arr, k)

标签： pythonperformance

解决方案

我会用n来表示数组的长度，用k来表示子数组的长度。

Ο( n )时间将是算法所花费的时间将与数组的长度成正比。即，长度为 1000 的数组的运行时间将是长度为 2000 的数组的运行时间的一半。

Ο( k ) 空间将是算法执行计算所需的内存量，与子数组的大小成正比。这样说来，它与输入的大小无关。

您的算法在进行 k 次迭代的循环上进行n - k + 1 次迭代。这使得它的执行时间大约为k × ( n - k + 1)。由于k可以随n变化，因此平均情况应为k = n/2，从而为您提供 Ο( n 2 ) 的运行时间。

您的算法占用的空间是 Ο(1)，因为您只需要几个整数变量。

推荐阅读