验证逻辑以找到给定算法的时间和 space 复杂度
Validate the logic to find the time and space complexity for the given algorithm
我需要确认我为以下算法计算时间和 space 复杂度的方法是否正确：
我有一个输入列表，我们可以以下面的为例：
[1,100,1,1,1,100,1,1,100,1] 并让我们将给定列表称为成本。我正在根据下面的算法修改给定列表
我的算法：
- 遍历列表（从位置 2 开始）直到输入列表的末尾。
- 我们执行以下操作：cost[i] = cost[i] + min(cost[i-1],cost[i-2])
- 我们最终检查最后两个元素并从最后两个元素中取最小值 = min = min(last element,second last element).
我计算时间复杂度的方法：
1. 对于步骤 1 = O(n)
2.对于步骤2 = O(1) + O(n)（计算两个元素中的最小值）
3. 对于步骤 3 = O(1)
因此时间复杂度 = O(n) + O(1) + O(n) + O(1) = O(n) 。 Space complexity = O(n) [简单假设 space 所需的是存储列表]。有人可以告诉我我计算复杂度的方法是否有效吗？
此致，
阿努巴夫
这是一个非常简单的动态规划算法。
如果您使用的是列表，那么您的最终答案就是正确的。但是，您实际上可以将 space 复杂度提高到 O(1)，因为您的动态编程递归是 "memoryless"，因为我们只需要前两个值来计算下一个值.因此，您可以只存储两个 "previous" 值，而不是存储整个列表。这个想法类似于 .
背后的想法
我需要确认我为以下算法计算时间和 space 复杂度的方法是否正确：
我有一个输入列表，我们可以以下面的为例： [1,100,1,1,1,100,1,1,100,1] 并让我们将给定列表称为成本。我正在根据下面的算法修改给定列表
我的算法：
- 遍历列表（从位置 2 开始）直到输入列表的末尾。
- 我们执行以下操作：cost[i] = cost[i] + min(cost[i-1],cost[i-2])
- 我们最终检查最后两个元素并从最后两个元素中取最小值 = min = min(last element,second last element).
我计算时间复杂度的方法： 1. 对于步骤 1 = O(n) 2.对于步骤2 = O(1) + O(n)（计算两个元素中的最小值） 3. 对于步骤 3 = O(1)
因此时间复杂度 = O(n) + O(1) + O(n) + O(1) = O(n) 。 Space complexity = O(n) [简单假设 space 所需的是存储列表]。有人可以告诉我我计算复杂度的方法是否有效吗？
此致， 阿努巴夫
这是一个非常简单的动态规划算法。
如果您使用的是列表，那么您的最终答案就是正确的。但是，您实际上可以将 space 复杂度提高到 O(1)，因为您的动态编程递归是 "memoryless"，因为我们只需要前两个值来计算下一个值.因此，您可以只存储两个 "previous" 值，而不是存储整个列表。这个想法类似于