为什么这个简单算法的最坏情况时间复杂度是 T(n/2) +1 而不是 n^2+T(n-1)？
Why is the worst case time complexity of this simple algorithm T(n/2) +1 as opposed to n^2+T(n-1)?
以下问题是关于大学最近的作业。我原以为答案是 n^2+T(n-1)，因为我认为 n^2 会使它的渐近时间复杂度为 O(n^2)。与 T(n/2)+1 一样，其渐近时间复杂度为 O(log2(n)).
答案已返回，事实证明正确答案是 T(n/2)+1 但是我不明白为什么会这样。
有人可以向我解释为什么这是该算法的最坏情况时间复杂度吗？可能我对时间复杂度的理解是错误的。
渐近时间复杂度n变大了。在您的示例中，由于问题指定 k 是固定的，因此唯一相关的复杂性是最后一个。见Wikipedia formal definition，具体为：
随着 n 增长到无穷大，递归支配 T(n) = T(n / 2) + 1。您也可以使用正式定义来证明这一点，基本上选择 x_0 = 10 * k 并证明可以使用前两种情况找到有限的 M。应该清楚 log(n) 和 n^2 都满足定义，因此更严格的界限是渐近复杂度。
O(f(n))是什么意思？这意味着时间最多为 c * f (n)，对于某些未知且可能很大的 c。
kevmo 声称复杂度为 O (log2 n)。好吧，你可以检查所有 n ≤ 10k 的值，并让 T (n) 的最大值为 X。X 可能相当大（我认为在这种情况下约为 167 k^3，但实际上并不重要).对于较大的 n，所需时间至多为 X + log2(n)。选择 c = X，这总是小于 c * log2 (n)。
当然，人们通常认为 O (log n) 算法会很快，而如果说 k = 10,000，这个算法肯定不会很快。所以你也了解到必须小心处理 O 符号。
以下问题是关于大学最近的作业。我原以为答案是 n^2+T(n-1)，因为我认为 n^2 会使它的渐近时间复杂度为 O(n^2)。与 T(n/2)+1 一样，其渐近时间复杂度为 O(log2(n)).
答案已返回，事实证明正确答案是 T(n/2)+1 但是我不明白为什么会这样。
有人可以向我解释为什么这是该算法的最坏情况时间复杂度吗？可能我对时间复杂度的理解是错误的。
渐近时间复杂度n变大了。在您的示例中，由于问题指定 k 是固定的，因此唯一相关的复杂性是最后一个。见Wikipedia formal definition，具体为：
随着 n 增长到无穷大，递归支配 T(n) = T(n / 2) + 1。您也可以使用正式定义来证明这一点，基本上选择 x_0 = 10 * k 并证明可以使用前两种情况找到有限的 M。应该清楚 log(n) 和 n^2 都满足定义，因此更严格的界限是渐近复杂度。
O(f(n))是什么意思？这意味着时间最多为 c * f (n)，对于某些未知且可能很大的 c。
kevmo 声称复杂度为 O (log2 n)。好吧，你可以检查所有 n ≤ 10k 的值，并让 T (n) 的最大值为 X。X 可能相当大（我认为在这种情况下约为 167 k^3，但实际上并不重要).对于较大的 n，所需时间至多为 X + log2(n)。选择 c = X，这总是小于 c * log2 (n)。
当然，人们通常认为 O (log n) 算法会很快，而如果说 k = 10,000，这个算法肯定不会很快。所以你也了解到必须小心处理 O 符号。