当时间复杂度根据 n 变化时算法 S 的最佳和最坏情况时间为 even/odd
Best and worst case time for Algorithm S when time complexity changes in accordance to n being even/odd
以下是家庭作业，所以我宁愿得到一些提示或一些信息来帮助我解决这个问题，而不是完整的答案。
Consider S an algorithm solution to a problem that takes as input an array A of size n. After analysis, the following conclusion was obtained:
Algorithm S executes an O(n)-time computation for each even number in A.
Algorithm S executes an O(logn)-time computation for each odd number in A.
What are the best and worst case time for algorithm S?
据此我了解到，时间复杂度根据 n 是偶数还是奇数而变化。换句话说，如果 n 是偶数，S 需要 O(n) 时间，当 n 是奇数时，S 需要 O(logn)。
采用两种增长率的最佳情况和最坏情况，并选择它们的边界是一件简单的事情吗？含义：
O(n) 的最佳情况是 O(1)，最坏情况是 O(n)。
O(logn) 的最佳情况是 O(logn)，最坏情况是 O(logn)。
因此算法 S 的最佳情况是 O(logn)，最坏情况是 O(n)？
我错过了什么吗？还是我在评估两种 big-Oh 的不同 best/worst 情况时错了？
第一次尝试:
好的，所以我完全误解了这个问题。感谢 candu，我现在可以更好地理解对我的要求，因此尝试更好地计算最佳和最坏情况。
似乎算法 S 根据 A 中的 EACH 数字改变了它的 运行时间。如果数字是偶数，运行时间是O(n)，如果数字是奇数，我们得到O(logn)。
最坏的情况将由 n 个偶数组成的数组 A 组成，对于每个数组，算法将 运行 O(n)。换句话说，算法 S 的最坏情况 运行time 应该是 n*O(n).
最好的情况将由 n 个奇数的数组 A 组成，对于每个，算法将 运行 O(logn)。算法 S 的最佳情况 运行time 应该是 n*O(logn)。
我说的有道理吗？那是真的吗:
算法 S 的最佳情况是 nO(logn)，最坏情况是 nO(n)？
如果是这样，是否可以重写？例如，O(log^n(n)) 和 O(n^n)？还是算术错误？
第二次尝试:
根据 JuanLopes 的回复，我似乎可以将 nO(n) 重写为 O(n*n) 或 O(n^2)，并将 nO(logn) 重写为 O(nlogn)。
现在算法 S 运行 在最佳情况下为 O(nlogn)，在最坏情况下为 O(n^2) 是否有意义？
这里有点混乱：算法 运行time 不取决于 n 是偶数还是奇数，而是取决于 A 中的数字是偶数还是奇数.
考虑到这一点，什么样的输入 A 会使算法 S 运行 更快？慢一点？
另外：说 O(n) 的最佳情况是 O(1) 是没有意义的。假设我有一个算法（"Algorithm Q"）是O(n)；我只能说存在一个常量 c，这样，对于大小为 n 的任何输入，算法 Q 花费的时间少于 cn。 不能保证我可以找到算法 Q 是 O(1) 的特定输入。
举个具体的例子，这需要线性时间无论传递什么输入:
def length(A):
len = 0
for x in A:
len += 1
return len
一些想法。
首先，没有提到渐近紧时间。所以一个 O(n) 算法实际上可以是一个 O(logn) 算法。所以想象一下这个算法在这种情况下的最佳情况 运行 时间。我知道，这有点挑剔。但这是作业，我想总是欢迎提及所有可能性。
其次，即使它是渐近紧的，也并不一定意味着它对所有元素都是紧的。考虑插入排序。对于每个要插入的新元素，我们需要在先前已排序的子数组中找到正确的位置。时间与子数组中元素的数量成正比，其上限为 O(n)。但这并不意味着每个新元素都需要恰好 #n 次比较才能插入。实际上，子数组越短，插入越快。
回到这个问题。 "executes an O(logn)-time computation for each odd number in A." 让我们假设所有奇数。可能第一个奇数需要 O(log1)，第二个奇数需要 O(log2)，.. 第 n 个需要 O(logn)。总的来说，它需要 O(logn!)。它与 "O(logn) for each odd number".
不矛盾
至于最坏的情况，你可以用大同小异的方式来分析。
以下是家庭作业，所以我宁愿得到一些提示或一些信息来帮助我解决这个问题，而不是完整的答案。
Consider S an algorithm solution to a problem that takes as input an array A of size n. After analysis, the following conclusion was obtained:
Algorithm S executes an O(n)-time computation for each even number in A.
Algorithm S executes an O(logn)-time computation for each odd number in A.
What are the best and worst case time for algorithm S?
据此我了解到，时间复杂度根据 n 是偶数还是奇数而变化。换句话说，如果 n 是偶数，S 需要 O(n) 时间，当 n 是奇数时，S 需要 O(logn)。
采用两种增长率的最佳情况和最坏情况，并选择它们的边界是一件简单的事情吗？含义：
O(n) 的最佳情况是 O(1)，最坏情况是 O(n)。
O(logn) 的最佳情况是 O(logn)，最坏情况是 O(logn)。
因此算法 S 的最佳情况是 O(logn)，最坏情况是 O(n)？
我错过了什么吗？还是我在评估两种 big-Oh 的不同 best/worst 情况时错了？
第一次尝试:
好的，所以我完全误解了这个问题。感谢 candu，我现在可以更好地理解对我的要求，因此尝试更好地计算最佳和最坏情况。
似乎算法 S 根据 A 中的 EACH 数字改变了它的 运行时间。如果数字是偶数，运行时间是O(n)，如果数字是奇数，我们得到O(logn)。
最坏的情况将由 n 个偶数组成的数组 A 组成，对于每个数组，算法将 运行 O(n)。换句话说，算法 S 的最坏情况 运行time 应该是 n*O(n).
最好的情况将由 n 个奇数的数组 A 组成，对于每个，算法将 运行 O(logn)。算法 S 的最佳情况 运行time 应该是 n*O(logn)。
我说的有道理吗？那是真的吗:
算法 S 的最佳情况是 nO(logn)，最坏情况是 nO(n)？
如果是这样，是否可以重写？例如，O(log^n(n)) 和 O(n^n)？还是算术错误？
第二次尝试:
根据 JuanLopes 的回复，我似乎可以将 nO(n) 重写为 O(n*n) 或 O(n^2)，并将 nO(logn) 重写为 O(nlogn)。
现在算法 S 运行 在最佳情况下为 O(nlogn)，在最坏情况下为 O(n^2) 是否有意义？
这里有点混乱：算法 运行time 不取决于 n 是偶数还是奇数，而是取决于 A 中的数字是偶数还是奇数.
考虑到这一点，什么样的输入 A 会使算法 S 运行 更快？慢一点？
另外：说 O(n) 的最佳情况是 O(1) 是没有意义的。假设我有一个算法（"Algorithm Q"）是O(n)；我只能说存在一个常量 c，这样，对于大小为 n 的任何输入，算法 Q 花费的时间少于 cn。 不能保证我可以找到算法 Q 是 O(1) 的特定输入。
举个具体的例子，这需要线性时间无论传递什么输入:
def length(A):
len = 0
for x in A:
len += 1
return len
一些想法。 首先，没有提到渐近紧时间。所以一个 O(n) 算法实际上可以是一个 O(logn) 算法。所以想象一下这个算法在这种情况下的最佳情况 运行 时间。我知道，这有点挑剔。但这是作业，我想总是欢迎提及所有可能性。
其次，即使它是渐近紧的，也并不一定意味着它对所有元素都是紧的。考虑插入排序。对于每个要插入的新元素，我们需要在先前已排序的子数组中找到正确的位置。时间与子数组中元素的数量成正比，其上限为 O(n)。但这并不意味着每个新元素都需要恰好 #n 次比较才能插入。实际上，子数组越短，插入越快。
回到这个问题。 "executes an O(logn)-time computation for each odd number in A." 让我们假设所有奇数。可能第一个奇数需要 O(log1)，第二个奇数需要 O(log2)，.. 第 n 个需要 O(logn)。总的来说，它需要 O(logn!)。它与 "O(logn) for each odd number".
不矛盾至于最坏的情况，你可以用大同小异的方式来分析。