看網(wǎng)上說可以吧歸并排序空間復雜度降到O(1),我有個小疑問,比如說二叉樹用遞歸實現(xiàn)空間復雜度即為O(logN),即為樹的高度,但是歸并排序遞歸實現(xiàn)不也都要把函數(shù)推入棧里面嗎,再加上額外需要的數(shù)組長度N,是不是空間復雜度是O(logN+N),所以最終是O(N)?謝謝
個人理解空間復雜度為O(1)的歸并排序是指內(nèi)存方面的空間復雜度,而忽略了堆棧里的O(logN)的空間復雜度(畢竟不在同一個空間)
//空間復雜度為O(1)的歸并排序
#include <iostream>
using namespace std;
void reverse_array(int a[], int n) {
int i = 0;
int j = n - 1;
while (i < j) {
swap(a[i], a[j]);
++i;
--j;
}
}
void exchange(int a[], int length, int length_left) {
reverse_array(a, length_left);
reverse_array(a + length_left, length - length_left);
reverse_array(a, length);
}
void Merge(int a[], int begin, int mid, int end) {
while (begin < mid && mid <= end) {
int step = 0;
while (begin < mid && a[begin] <= a[mid])
++begin;
while (mid <= end && a[mid] <= a[begin]) {
++mid;
++step;
}
exchange(a + begin, mid - begin, mid - begin - step);
}
}
void MergeCore(int a[], int left, int right) {
if (left < right) {
int mid = (left + right) / 2;
MergeCore(a, left, mid);
MergeCore(a, mid + 1, right);
Merge(a, left, mid + 1, right);
}
}
void MergeSort(int a[], int length) {
if (a == NULL || length < 1)
return;
MergeCore(a, 0, length - 1);
}
int main() {
int a[] = {1,0,2,9,3,8,4,7,6,5,11,99,22,88,11};
int length = sizeof(a) / sizeof(int);
MergeSort(a, length);
for (int i = 0; i < length; i++)
cout << a[i] << " ";
cout << endl;
return 0;
}
歸并如果是自上而下遞歸需要壓棧,但因為歸分二分的界限是相對固定的,所以如果自下而上實現(xiàn)的話,不需要遞歸,都是數(shù)組的原位交換位置,并不需要申請額外的空間.
數(shù)組本身存儲O(N)的空間, 如果是O(1)我想可能指的是類似滑動窗口,每次只是讀取當前的需要比較的數(shù)據(jù).不過效率...
這里有原位歸并排序的論文, 可以參考下
It is shown that an array of n elements can be sorted using O(1) extra space,
O(n log n= log log n) element moves, and n log2 n + O(n log log n) comparisons. This
is the rst in-place sorting algorithm requiring o(n log n) moves in the worst case
while guaranteeing O(n log n) comparisons but, due to the constant factors involved,
the algorithm is predominantly of theoretical interest.
北大青鳥APTECH成立于1999年。依托北京大學優(yōu)質(zhì)雄厚的教育資源和背景,秉承“教育改變生活”的發(fā)展理念,致力于培養(yǎng)中國IT技能型緊缺人才,是大數(shù)據(jù)專業(yè)的國家
北大青鳥中博軟件學院創(chuàng)立于2003年,作為華東區(qū)著名互聯(lián)網(wǎng)學院和江蘇省首批服務外包人才培訓基地,中博成功培育了近30000名軟件工程師走向高薪崗位,合作企業(yè)超4
中公教育集團創(chuàng)建于1999年,經(jīng)過二十年潛心發(fā)展,已由一家北大畢業(yè)生自主創(chuàng)業(yè)的信息技術與教育服務機構,發(fā)展為教育服務業(yè)的綜合性企業(yè)集團,成為集合面授教學培訓、網(wǎng)
達內(nèi)教育集團成立于2002年,是一家由留學海歸創(chuàng)辦的高端職業(yè)教育培訓機構,是中國一站式人才培養(yǎng)平臺、一站式人才輸送平臺。2014年4月3日在美國成功上市,融資1
曾工作于聯(lián)想擔任系統(tǒng)開發(fā)工程師,曾在博彥科技股份有限公司擔任項目經(jīng)理從事移動互聯(lián)網(wǎng)管理及研發(fā)工作,曾創(chuàng)辦藍懿科技有限責任公司從事總經(jīng)理職務負責iOS教學及管理工作。
浪潮集團項目經(jīng)理。精通Java與.NET 技術, 熟練的跨平臺面向?qū)ο箝_發(fā)經(jīng)驗,技術功底深厚。 授課風格 授課風格清新自然、條理清晰、主次分明、重點難點突出、引人入勝。
精通HTML5和CSS3;Javascript及主流js庫,具有快速界面開發(fā)的能力,對瀏覽器兼容性、前端性能優(yōu)化等有深入理解。精通網(wǎng)頁制作和網(wǎng)頁游戲開發(fā)。
具有10 年的Java 企業(yè)應用開發(fā)經(jīng)驗。曾經(jīng)歷任德國Software AG 技術顧問,美國Dachieve 系統(tǒng)架構師,美國AngelEngineers Inc. 系統(tǒng)架構師。