Python中的时空分析

Question

有人可以提供一个关于时间和空间的O（log（n））和O（nlog（n））问题的例子吗？

我对这种类型的分析很陌生，看不到过去的多项式时间/空间。

我不明白的是你如何成为O（1）<O（log（n））

此外，我将不胜感激地介绍涉及这些案例的所有很好的例子（时空）：

我发现空间分析的模棱两可，因此与在同一地点进行时间分析的其他情况相比，很高兴看到它-我在网上找不到可靠的东西。

您能提供每种情况的时空示例吗？分析？

Answer 1

首先，我想指出一个事实，我们发现算法的Time Complexity或Space Complexity，而不是编程语言的。如果您考虑计算任何程序的时间复杂度，我只能建议您选择C。从技术上讲，在python中计算Time Complexity非常困难。

示例：假设您正在创建一个列表，并在for循环的每一遍对其进行排序，例如[]

n = int(input())

for i in range(n):
    l.append(int(input())
    l = sorted(l)
[乍看之下，我们的直觉是它的时间复杂度为O(n)，但是仔细检查后，会发现sorted()函数正在被调用，众所周知，任何排序算法都可以不小于O(n log n)（除了具有O(kn)和O(n+k)时间复杂度的基数和计数排序），因此此代码的最小时间复杂度将为O(n^2 log n)。

[我建议您阅读一些不错的Data Structure and Algorithm书，以更好地理解。您可以购买B.Tech或B.E.课程。希望这对您有所帮助：）

Answer 2

这是一个相当琐碎的答案：无论您拥有什么公式f（n