Thứ nhất, đây là mã Shell sắp xếp của tôi (sử dụng Java):Độ phức tạp của thời gian đối với Shell sắp xếp?
public char[] shellSort(char[] chars) {
int n = chars.length;
int increment = n/2;
while(increment > 0) {
int last = increment;
while(last < n) {
int current = last - increment;
while(current >= 0) {
if(chars[current] > chars[current + increment]) {
//swap
char tmp = chars[current];
chars[current] = chars[current + increment];
chars[current + increment] = tmp;
current -= increment;
}
else { break; }
}
last++;
}
increment /= 2;
}
return chars;
}
này thực hiện đúng Shell sort là (quên cho bây giờ về trình tự khoảng cách hiệu quả nhất - ví dụ, 1,3,7,21. ..)? Tôi hỏi vì tôi đã nghe nói rằng sự phức tạp thời gian tốt nhất cho Shell Sort là O (n). (Xem http://en.wikipedia.org/wiki/Sorting_algorithm). Tôi không thể thấy mức hiệu quả này được nhận ra bởi mã của tôi. Nếu tôi thêm heuristics vào nó, thì yeah, nhưng khi nó đứng, không.
Điều đó đang được nói, câu hỏi chính của tôi bây giờ - Tôi đang gặp khó khăn khi tính toán độ phức tạp thời gian Big O cho việc triển khai sắp xếp Shell của tôi. Tôi xác định rằng vòng lặp ngoài cùng nhất là O (log n), vòng giữa là O (n) và vòng lặp bên trong nhất cũng là O (n), nhưng tôi nhận ra hai vòng bên trong sẽ không thực sự là O (n) - chúng sẽ ít hơn nhiều so với điều này - chúng nên là gì? Bởi vì rõ ràng thuật toán này chạy hiệu quả hơn nhiều so với O ((log n) n^2).
Bất kỳ hướng dẫn nào được đánh giá cao vì tôi rất lạc lõng! : P
Xem [shell-sort-java-example] (http://stackoverflow.com/questions/4833423/shell-sort-java-example) – nawfal