|
Turli xil algoritmlar uchun ish vaqti taxminlari
T (N) algoritmning bajarilish vaqtini belgilasin. Oʻrganilayotgan algoritm quyidagi shaklga ega boʻlsin:
1. faqat asosiy operatsiyalarni oʻz ichiga olgan koʻrsatmalar toʻplami:
1-bayonot;
...
bayonot k;
Keyin T (N) \u003d T (1-bayonot) + ... + T (k bayonot).
Chunki har bir koʻrsatma faqat asosiy operatsiyalarni oʻz ichiga oladi, keyin ushbu kod qismini bajarish vaqti kirish maʻlumotlarining oʻlchamiga bogʻliq emas (u kirish maʻlumotlarining kattaligi bilan oʻsmaydi), yaʻni. doimiy. Ushbu algoritm O (1) murakkablikka ega.
2. if-else bayonotlari
Agar (shart) (
bayonotlar ketma-ketligi 1
}
boshqa (
bayonotlar ketma-ketligi 2
}
Bu erda 1-sonli bayonotlar yoki 2-sonli ketma-ketliklar bajariladi, shuning uchun biz T (N) \u003d max (T (bayonotlar ketma-ketligi 1), T (bayonotlar ketma-ketligi 2)) boʻyicha eng yomon ishni bajarish vaqtini taxmin qilishni istaymiz. Masalan, 1-gaplar ketma-ketligini bajarish vaqti O (N), bayonotlar ketma-ketligi O (1) boʻlsa, u holda T (N) \u003d O (N).
Uchun (i \u003d 0; i< N; i++) {
bayonotlar ketma-ketligi
}
Chunki tsikl N marta bajariladi, keyin bayonotlar ketma-ketligi ham N marta bajariladi. Agar T (bayonotlar ketma-ketligi) \u003d O (1) boʻlsa, unda T (N) \u003d O (N) * O (1) \u003d O (N).
4. Ichki halqalar.
Uchun (i \u003d 0; i< N; i++) {
uchun (j \u003d 0; j< M; j ++){
...
}
}
Tashqi tsikl N marta bajariladi. Har safar tashqi tsikl bajarilganda ichki tsikl M bajariladi
Endi ushbu kodni koʻrib chiqing:
Uchun (i \u003d 0; i< N; i++) {
uchun (j \u003d i + 1; j< N; j ++){
bayonotlar ketma-ketligi
}
}
Ichki tsiklning takrorlanish soni tashqi tsiklning takrorlanishiga qarab oʻzgarishini koʻrib chiqamiz.
I tsikl j (bajarilish vaqti soni)
0 N
1 N-1
2 N-2
...
N-1 1
Keyin bayonotlar ketma-ketligi N + N-1 + ... + 1 marta bajariladi. Bunday miqdorlarni tezda hisoblash uchun matematik tahlildan olingan formulalar, bu holda formulalar foydalidir
Oʻsha. ushbu algoritm murakkablikka ega boʻladi (O (N ^ 2) \\).
Va bu erda bunday holatlar uchun foydali boʻlgan eng koʻp ishlatiladigan formulalar:
4. Tasdiqlash usulni chaqirishni oʻz ichiga oladigan boʻlsa, tasdiqlashning bajarilish vaqtini hisoblash usulni bajarish vaqtini hisoblash asosida hisoblanadi. Masalan; misol uchun:
uchun (j \u003d 0; j< N; j ++){
Agar usulning bajarilish vaqti \\ (g (N) \u003d O (N) \\) boʻlsa, u holda \\ (T (N) \u003d O (N) * O (N) \u003d O (N ^ 2) \\).
5. Ikkilik (ikkilik) qidirish.
Int l \u003d 0;
int u \u003d A. uzunlik - 1
int m;
esa (l<= u) {
m \u003d l + (u - 1) / 2
agar A [m]< k {
l \u003d m +1;
}
aks holda A [m] \u003d\u003d k (
qaytish m;
}
boshqa (
u \u003d m - 1;
}
}
qaytish -1;
Ikkilik qidirish tartiblangan massivda k sonining indeksini topishga imkon beradi, agar bu raqam unda boʻlmasa -1 qaytariladi. Birinchidan, biz k ni massivning oʻrtasidagi raqam bilan taqqoslaymiz. Agar k bu sondan kichik boʻlsa, unda biz uni qatorning chap yarmidan, agar koʻproq boʻlsa, oʻng yarmidan qidirishimiz kerak. Keyin k oldingi bosqichda tanlangan massivning yarmi oʻrtasidagi raqam bilan taqqoslanadi va hokazo. Har bir takrorlash bilan qidiruv maydoni ikki baravar kamayadi. Savol tugʻiladi: eng yomon holatda qancha takrorlash kerak boʻladi (yaʻni massivda k ga teng son topilmasa va taqqoslash uchun maʻlumotlar qolmasa).
Koʻrayapmizki, 1 ta takrorlashdan keyin \\ (N / 2 \\) indeksni qidirish uchun maʻlumotlar qoladi, 2 ta takrorlashdan keyin ((N / 4 \\) maʻlumotlar, 3 ta takrorlashdan keyin - \\ (N / 8) \\) va boshqalar. \\ (\\ Frac (N) (2 ^ x) \u003d 1 \\) tenglamani echish orqali eng yomon takrorlanish sonini bilib olamiz. Ushbu tenglama \\ (2 ^ x \u003d N \\) tenglamaga teng, shuning uchun \\ (x \u003d log_ (2) (N) \\) yoki \\ (x \u003d lg (N) \\) (logaritma taʻrifiga qarang) . Shuning uchun ikkilik qidirish algoritmi uchun murakkablik bahosi \\ (O (logN) \\) dir.
Yaxshi yangilik shundaki, koʻpgina algoritmlarning bajarilish vaqtini tavsiflash uchun faqat bir nechta funktsiyalar etarli: \\ (1, logN, N, NlogN, N ^ 2, N ^ 3, 2 ^ N \\). Grafik kiritilgan maʻlumotlarning hajmiga qarab algoritmni bajarish vaqtining turli xil oʻsish surʻatlarini aks ettiradi:
Ushbu grafik, xususan, algoritmning bajarilish vaqti "logaritmik" boʻlsa, yaʻni. algoritm murakkablikka ega \\ (O (logN) \\), keyin bu juda ajoyib, chunki uning bajarilish vaqti kirish maʻlumotlarining kattalashishi bilan juda sekin oʻsib boradi, agar bajarish vaqti chiziqli ravishda kiritilgan maʻlumotlarning hajmiga bogʻliq boʻlsa, unda bu ham yomon emas, lekin eksponent ish vaqti algoritmlari (\\ (O (2) ^ N) \\)) umuman ishlatmaslik yoki faqat juda kichik maʻlumotlarda ishlatgan maʻqul.
Do'stlaringiz bilan baham: |
