通过减少确定解决方案的时间复杂度
Determining time complexity of solution by reductions
假设您找到了 A 问题的解决方案并试图了解其复杂性。您通过总共调用 B 子例程 n^2 次并执行恒定量的额外工作来解决 A。
如果B是选择排序，这个解的时间复杂度是多少？
如果B是归并排序，这个解的时间复杂度是多少？
我对第一个问题的回答是 n^2，对第二个问题的回答是 nlogn。对我的回答有任何想法都将不胜感激。
是的，你是对的，
O(B) = n ^ 2 -> 选择排序；
O(B) = n * log(n)。 -> Marge 排序
我假设“解决方案”是指“算法”，而“此解决方案”是指通过调用 B n^2 次来解决问题 A 的算法.此外，我假设 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).
假设您找到了 A 问题的解决方案并试图了解其复杂性。您通过总共调用 B 子例程 n^2 次并执行恒定量的额外工作来解决 A。
如果
B是选择排序，这个解的时间复杂度是多少？如果
B是归并排序，这个解的时间复杂度是多少？
我对第一个问题的回答是 n^2，对第二个问题的回答是 nlogn。对我的回答有任何想法都将不胜感激。
是的，你是对的， O(B) = n ^ 2 -> 选择排序； O(B) = n * log(n)。 -> Marge 排序
我假设“解决方案”是指“算法”，而“此解决方案”是指通过调用 B n^2 次来解决问题 A 的算法.此外，我假设 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).