Variant №59 Eng yaxshi, oʼrtacha va eng yomon algoritmlar. Matritsaga yangi element qoʼshish algoritmi, misol keltiring. Qoʼyish orqali saralash algoritmlarining tahlili. Javoblar

public int ChiziqliQidiruv(int[] a, int t)

{

for (int i = 0; i < a.Length; i++)

if (t == a[i])

return i;

return -1;}

Biz qidirayotgan son massivning birinchi indeksida yotgan bo'lsin. Bu algoritmning eng yaxshi xolati deyiladi sababi, for atigi bir marta ishlaydi. Endi aksincha kerakli son massivning eng so'ngida yotgan bo'lsin. Bu algoritmning eng yomon holati deyiladi. Sabab esa, algoritm massivning xar bir elementini tekshirib chiqishga majburligidir. Agar ush dasturni bir necha marta va xar hil o'lchamdagi massivlar bilan qaytarsak for n/2 marta ishlaydi va bu algoritmning o'rta holati deyiladi.Odatda eng yaxshi holat e'tiborga olinmaydi. Sababi bu holat juda kamdan kam uchraydi va algoritmning ishlash vaqtini hisoblayotganimizda juda ham optimistik holat hisoblanadi. Boshqacha qilib aytganda bu holat orqali algoritmning husisiyatini to'liq ifodalab bo'lmaydi. Boshqa tarafdan esa, saralash algoritmlaridan birida eng yaxshi holatning uchrash extimolligi juda yuqori, bu vaziyatda eng yaxshi holatni ham e'tiborga olishimiz kerak bo'ladi. Nasib qilsa keyin maqolalarimizdan biridi ushbu saralash algoritmga to'xtalib o'tamiz.Eng yomon holat haqidachi? Analiz vaqtida algoritim eng kamida shu holat darajasida yaxshi bo'lishini oldindan bilasiz. Ya'ni algoritm bajarishi mumkin bo'lgan operatsiyalarni maksimum darajada bajaradi. Shu sababdan, algoritmning eng yomon holatini yaxshilash orqali algoritmning ishlash vaqtida o'sishga erishasiz. Algoritmlar analizida ko'pincha shu holat e'tiborga olinadi.

2.Matritsaga yangi element qoʼshish algoritmi, misol keltiring.

Qanday qilib Java-da Matritsa-ga yangi element qo'shish kerak?

N M kattalikdagi matritsani hisobga olsak, Java-ga ushbu satr yoki ustunga x element qo'shish kerak.

Massivning o'lchamini C / C ++ da bajarilgandek Java-da dinamik ravishda o'zgartirish mumkin emas. Shunday qilib, matritsaga element qo'shish uchun quyidagi usullardan birini bajarish mumkin:
Yangi matritsa yaratish orqali:

N + 1 o'lchamdagi yangi qatorni yarating, bu erda n asl massivning o'lchami.

Ushbu qatorga asl qatorning n elementlarini qo'shing.

N + 1-chi pozitsiyada yangi elementni qo'shing.

Yangi qatorni chop eting.

Quyida yuqoridagi yondashuvning bajarilishi:

Misol:

Matrisaning k satri oldidan element qo'shadi

import java.util.Scanner;
/**

* Created by User on 26.04.2020.

*/

public class AddElementToMatrix {

public static void main(String[] args) {

Scanner S = new Scanner(System.in);

int m = S.nextInt();

int n = S.nextInt();

int[][] a = new int[m][n];

for (int i = 0; i < m; i++) {

for (int j = 0; j < n; j++) {

a[i][j] = (int) (Math.random() * 20);

System.out.print(a[i][j] + "\t");

}

System.out.println();

}

int k = S.nextInt();

int[][] b = new int[m + 1][n];

for (int i = 0, j = 0; i < b.length; i++) {

if (i == k) {

b[i] = new int[n];

continue;

}

b[i] = a[j++];

}

a = b;

for (int i = 0; i < a.length; i++) {

for (int j = 0; j < n; j++) {

System.out.print(a[i][j] + "\t");

}

System.out.println();

}
}

}

3.Qoʼyish orqali saralash algoritmlarining tahlili.

Oʼrniga qoʼyish algoritmi ham O(n2) saralash algoritmlariga kiradi. Boshqa kvadratik murakkablikdagi saralash algoritmlaridan farqli oʼlaroq, bu saralash amalda kichik maʼlumotli massivlarni saralash uchun qoʼllaniladi. Masalan, test saralash yoʼnalishini yaxshilash uchun ishlatiladi. Аyrim manbalarga koʼra odamlar bunday algoritmlarni raqamlarni sarflash uchun ishlatadi. Oʼrniga qoʼyish algoritmi ham tanlash saralash algoritmiga oʼxshash. Massiv hayolan ikkiga: saralangan va saralanmagan qismlarga boʼlinadi. Boshlanishida, saralangan qismi massivning birinchi elementini oladi, saralanmagan qismi esa qolgan elementlarni oladi. Har qadamda, algoritm birinchi saralanmagan qismning birinchi elementini oladi va saralangan qismning kerakli joyiga qoʼyadi. Saralanmagan qism bosh boʼlib qolganda

algoritm toʼxtaydi. Formallaganda, oʼrniga qoʼyish algoritmi qadamlari bunga oʼxshash:

Қўйиш орқали саралаш

Obʼektlarsaralangan a(1),...,a(i-1) va saralanmagan a(i),...,a(n) kabi 2 ta ketma-ketliklarga boʼlinadi. Har bir qadamda (i=2 dan boshlab) saralanmagan ketma-ketlikdan i-chi element ajratib olinib saralangan ketma-ketlikning kerakli joyiga qoʼshiladi.

Қўйиш орқали саралаш алгоритми самарадорлиги

Таққослашлар сони:



Ўринлаштиришлар сони:



Саралашга кетган вақт: