说我想将项目插入排序的堆栈s。我创建一个临时堆栈S2。我一直将它们推入S2并将其从S1弹出,直到到达要插入的位置为止。然后我将其推到s。然后,我将S2中的所有内容都推回S。假设s的大小是n,此操作的时间复杂性是多少?我很确定是O(n(。因为您在s中的大多数n元素中弹出,然后弹出S2中的大多数n个项目。这给了您O(n( O(n(,即O(n(。是的吗?
#include <iostream>
#include <stack>
using namespace std;
void insert(int item, stack<int> &s){
stack<int> temp;
while(s.top() > item){
int curr = s.top();
s.pop();
temp.push(curr);
}
s.push(item);
while(!temp.empty()){
int curr = temp.top();
s.push(curr);
temp.pop();
}
}
int main(){
int numbers[] = {1,2,4,5,6};
stack<int> s;
for (int i = 0; i < 5; i+=1){
s.push(numbers[i]);
std::cout << "original s: " << s.top() << std::endl;}
insert(3, s);
for (int i = 0; i < 6; i+=1){
std::cout << "new s: " << s.top() << std:: endl;
s.pop();}
}
如您所见,该代码完全按照我的预期工作。但是,我听说此算法(使用临时堆栈(与优先队列有关。它的插入函数是o(logn(而不是o(n(。谁能为我澄清此处显示的插入方法的正确时间复杂性?
我也想知道插入方法的空间复杂性:
我的分析:您宣布了最大尺寸n的温度堆栈。同样,在循环内部,您每次运行循环时都会声明一个新的温度。因此,空间复杂性也为o(n(。这是对的吗?
P.S。我知道我不应该使用名称空间。这仅是为了方便的。
好吧,我不知道您在谈论什么插入算法。但是,将元素插入优先级队列具有 o(log n(的复杂性。当然,在这种情况下,您的元素将按降序(默认行为(进行排序,或者使用您自己提供的比较函数。最终结果将足够接近您的代码;由于您也将元素整理成
要回答您的问题,是的,当然,您的代码的复杂性是 o(n(。
您算法与O(n)
一起使用,并且在具有O(logN)
复杂性的数组或堆栈上无法实现插入,最坏的情况总是O(N)
。同样,排序的数组插入比未分类的数组要慢。原因是当我们插入元素及其需要纠正时,元素的顺序会发生变化。堆栈也是如此,除非您不想在插入后保留订单。