time-complexity - 通过约简确定解的时间复杂度

Question

假设您找到了A问题的解决方案并试图了解它的复杂性。你A通过调用你的B子例程总共 n^2 次来解决，并且还做了大量的额外工作。

1. 如果B是选择排序，这个解决方案的时间复杂度是多少？

2. 如果B是归并排序，这个解决方案的时间复杂度是多少？

我对第一个问题的回答是n^2，对第二个问题的回答是nlogn。任何想法都将不胜感激我的回答。

标签： time-complexitymergesortpolynomialsselection-sortreduction

Answer 1

我假设“解决方案”是指“算法”，而“这个解决方案”是指A通过调用B n^2时间来解决问题的算法。此外，我假设n您的意思是输入的大小。

那么如果B是选择排序，这是一种O(n^2)算法，那么求解的算法A就是O(n^2 * n^2) = O(n^4)。

如果B是归并排序，即O(n log n)，则求解算法A为O(n^2* n log n) = O(n^3 log n)。