مرتبه زمانی

مرتبه زمانی متوسط(تتا) insertion sort را با مراحل بدست آوردن آنرا اگه بگذارید ممنون میشم:10:

از سايت ويكيپديا
تو اين جدول زمان متوسط همون تتاست.

[ برای مشاهده لینک ، با نام کاربری خود وارد شوید یا ثبت نام کنید ]

سلام

کد:

---

void insertionSort(ArrayList vals){ 
for(int i=1; i<vals.size(); ++i) { 
  int j=i-1; 
 while(j>=0 && vals.get(j+1)<vals.get(j)) { 
    swap(vals.get(j), vals.get(j+1)); 
    --j; 
 }
 }
}

---

In the worst case, the while loop runs i-1 times for each time the for loop is run. The first time the for loop runs, i=1 so the while loop runs 0 times. The next time i=2 so the while loop runs 1 time. Hopefully you see a pattern of 0 + 1 + 2 + 3 + ... + n-2 which is O(n2) where n is the number of elements in the collection.

منبع:

کد:

---

http://www.t-a-y-l-o-r.com/msoe/viewtopic.php?id=144

---

اگه توضیحاتش کافی نبود،بگین تا واستون بیشتر توضیح بدم:20: