python 中的时间和 Space 分析
Time and Space analysis in python
Can someone provide an example of O(log(n)) and O(nlog(n)) problems for both time and space?
我对这种类型的分析很陌生，看不到过去的多项式 time/space。
What I don't get is how can you be O(1) < O(log(n)) < O(n) is that
like "semi-constant"?
此外，如果有任何涵盖这些情况（包括时间和 space）的优秀示例，我将不胜感激：
我发现 space 分析有点模棱两可，因此与同一地点的时间分析的其他案例相比，我会很高兴看到它——这是我无法在网上可靠地找到的东西。
Can you provide examples for each case in both space and time
analysis?
首先，我想指出一个事实，即我们发现 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 规定的书。课程。希望这对你有帮助:)
这是一个相当简单的答案：无论您有什么公式 f(n)，以下算法 运行 in O(f(n )) 时间和 space，只要 f 本身计算速度不是太慢。
def meaningless_waste_of_time(n):
m = f(n)
for i in range(int(m)):
print('foo')
def meaningless_waste_of_space(n):
m = f(n)
lst = []
for i in range(int(m)):
lst.append('bar')
例如，如果您定义 f = lambda n: (n ** 2) * math.log(n)，那么时间和 space 复杂度将为 O(n² log n) 分别.
在示例之前，对大 O 符号进行一些澄清
也许我看错了，但是看到
What I don't get is how can you be O(1) < O(log(n)) < O(n) is that like "semi-constant"?
让我觉得您已经了解了 big-O 表示法作为要执行的操作数（或要存储的字节数等）的想法，例如 如果你有一个循环 for(int i=0;i<n;++i) 那么就有 n 个操作所以时间复杂度是 O(n)。虽然这是一个很好的第一直觉，但我认为它可能会产生误导，因为大 O 符号定义了更高的渐近界限。
假设您选择了一种算法来对数字数组进行排序，让我们表示 x 该数组中元素的数量，以及 f(x) 该算法的时间复杂度。现在假设我们说算法是O(g(x))。这意味着随着 x 的增长，我们最终将达到阈值 x_t，如果 x_i>x_t，则 abs(f(x_i)) 将始终低于或等于 alpha*g(x_i) 其中 alpha 是正实数。
因此，O(1) 的函数并不总是需要相同的常数时间，相反，您可以确定无论需要多少数据，完成所需的时间它的任务将低于固定的时间量，例如 5秒。同样，O(log(n)) 并不意味着有任何半常数的概念。这只是意味着 1) 算法所花费的时间将取决于您提供给它的数据集的大小，以及 2) 如果数据集足够大（即 n足够大）那么它完成所需的时间总是小于或等于 log(n)。
关于时间复杂度的一些例子
O(1): 访问数组中的元素。O(log(n)): binary search 在递增排序的数组中。假设您有一个 n 元素的数组，并且您想要找到值等于 x 的索引。您可以从数组的中间开始，如果您读取的值 v 大于 x，则在 v 的左侧重复相同的过程，如果v 的右侧看起来更小。您继续此过程，直到找到您要查找的值。可以看到，如果运气好，第一次可以找到数组中间的值，也可以在log(n)次操作后找到。所以不存在半恒常性，Big-O表示法告诉你最坏的情况。O(nlogn)：使用Heap sort对数组进行排序。这有点太长了，无法在这里解释。 O(n^2)：计算正方形灰度图像上所有像素的总和（您可以将其视为二维数字矩阵）。 O(n^3)：简单地将两个大小为 n*n 的矩阵相乘。 O(n^{2+epsilon})：以智能方式乘以矩阵 (see wikipedia)O(n!) 天真地计算阶乘。
一些关于 space 复杂度的例子
O(1) 堆排序。有人可能会认为，由于您需要从树的根部删除变量，因此您将需要额外的 space。但是，由于堆只能作为数组实现，因此您可以将删除的值存储在所述数组的末尾，而不是分配新的 space.我认为，一个有趣的例子是比较经典问题的两个解决方案：假设您有一个整数数组 X 和一个目标值 T，并且你被保证在 X 中存在两个值 x,y 使得 x+y==T。您的目标是找到这两个值。
一种解决方案（称为双指针）是使用堆排序 (O(1) space ) 对数组进行排序，然后定义两个索引 i,j 分别指向排序的开始和结束数组 X_sorted。然后，如果 X[i]+X[j]<T，我们增加 i，如果 X[i]+X[j]>T，我们减少 j。我们在 X[i]+X[j]==T 时停止。很明显，这不需要额外的分配，因此解决方案具有 O(1) space 的复杂性。第二种解决方案是：
D={}
for i in range(len(X)):
D[T-X[i]]=i
for x in X:
y=T-x
if y in D:
return X[D[y]],x
由于字典的原因，它具有 space 的复杂性 O(n)。
上面给出的时间复杂度示例（关于有效矩阵乘法的示例除外）推导起来非常简单。正如其他人所说，我认为阅读有关该主题的书是深入理解该主题的最佳选择。我强烈推荐Cormen's book。
Can someone provide an example of O(log(n)) and O(nlog(n)) problems for both time and space?
我对这种类型的分析很陌生，看不到过去的多项式 time/space。
What I don't get is how can you be O(1) < O(log(n)) < O(n) is that like "semi-constant"?
此外，如果有任何涵盖这些情况（包括时间和 space）的优秀示例，我将不胜感激：
我发现 space 分析有点模棱两可，因此与同一地点的时间分析的其他案例相比，我会很高兴看到它——这是我无法在网上可靠地找到的东西。
Can you provide examples for each case in both space and time analysis?
首先，我想指出一个事实，即我们发现 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 规定的书。课程。希望这对你有帮助:)
这是一个相当简单的答案：无论您有什么公式 f(n)，以下算法 运行 in O(f(n )) 时间和 space，只要 f 本身计算速度不是太慢。
def meaningless_waste_of_time(n):
m = f(n)
for i in range(int(m)):
print('foo')
def meaningless_waste_of_space(n):
m = f(n)
lst = []
for i in range(int(m)):
lst.append('bar')
例如，如果您定义 f = lambda n: (n ** 2) * math.log(n)，那么时间和 space 复杂度将为 O(n² log n) 分别.
在示例之前，对大 O 符号进行一些澄清
也许我看错了，但是看到
What I don't get is how can you be O(1) < O(log(n)) < O(n) is that like "semi-constant"?
让我觉得您已经了解了 big-O 表示法作为要执行的操作数（或要存储的字节数等）的想法，例如 如果你有一个循环 for(int i=0;i<n;++i) 那么就有 n 个操作所以时间复杂度是 O(n)。虽然这是一个很好的第一直觉，但我认为它可能会产生误导，因为大 O 符号定义了更高的渐近界限。
假设您选择了一种算法来对数字数组进行排序，让我们表示 x 该数组中元素的数量，以及 f(x) 该算法的时间复杂度。现在假设我们说算法是O(g(x))。这意味着随着 x 的增长，我们最终将达到阈值 x_t，如果 x_i>x_t，则 abs(f(x_i)) 将始终低于或等于 alpha*g(x_i) 其中 alpha 是正实数。
因此，O(1) 的函数并不总是需要相同的常数时间，相反，您可以确定无论需要多少数据，完成所需的时间它的任务将低于固定的时间量，例如 5秒。同样，O(log(n)) 并不意味着有任何半常数的概念。这只是意味着 1) 算法所花费的时间将取决于您提供给它的数据集的大小，以及 2) 如果数据集足够大（即 n足够大）那么它完成所需的时间总是小于或等于 log(n)。
关于时间复杂度的一些例子
O(1): 访问数组中的元素。O(log(n)): binary search 在递增排序的数组中。假设您有一个n元素的数组，并且您想要找到值等于x的索引。您可以从数组的中间开始，如果您读取的值v大于x，则在v的左侧重复相同的过程，如果v的右侧看起来更小。您继续此过程，直到找到您要查找的值。可以看到，如果运气好，第一次可以找到数组中间的值，也可以在log(n)次操作后找到。所以不存在半恒常性，Big-O表示法告诉你最坏的情况。O(nlogn)：使用Heap sort对数组进行排序。这有点太长了，无法在这里解释。O(n^2)：计算正方形灰度图像上所有像素的总和（您可以将其视为二维数字矩阵）。O(n^3)：简单地将两个大小为n*n的矩阵相乘。O(n^{2+epsilon})：以智能方式乘以矩阵 (see wikipedia)O(n!)天真地计算阶乘。
一些关于 space 复杂度的例子
O(1)堆排序。有人可能会认为，由于您需要从树的根部删除变量，因此您将需要额外的 space。但是，由于堆只能作为数组实现，因此您可以将删除的值存储在所述数组的末尾，而不是分配新的 space.我认为，一个有趣的例子是比较经典问题的两个解决方案：假设您有一个整数数组
X和一个目标值T，并且你被保证在X中存在两个值x,y使得x+y==T。您的目标是找到这两个值。 一种解决方案（称为双指针）是使用堆排序 (O(1)space ) 对数组进行排序，然后定义两个索引i,j分别指向排序的开始和结束数组X_sorted。然后，如果X[i]+X[j]<T，我们增加i，如果X[i]+X[j]>T，我们减少j。我们在X[i]+X[j]==T时停止。很明显，这不需要额外的分配，因此解决方案具有O(1)space 的复杂性。第二种解决方案是：D={} for i in range(len(X)): D[T-X[i]]=i for x in X: y=T-x if y in D: return X[D[y]],x由于字典的原因，它具有 space 的复杂性
O(n)。
上面给出的时间复杂度示例（关于有效矩阵乘法的示例除外）推导起来非常简单。正如其他人所说，我认为阅读有关该主题的书是深入理解该主题的最佳选择。我强烈推荐Cormen's book。