Oraliq nazorat Nº1

Dasturning C#dagi matni:
using System;
using System.Linq;

class Program

{
static void Main()
{
double[] sonlar = { 1.2, 3.4, 5.6, 7.8 }; // haqiqiy sonlar uchun misol
int n = sonlar.Length / 2;
double min = sonlar[0] + sonlar[2 * n - 1];
for (int i = 1; i < n; i++)
{
double jami = sonlar[i] + sonlar[2 * n - 1 - i];
if (jami < min)
{
min = jami;
}
}
Console.WriteLine(min);
Console.ReadKey();
}
}
Natija:

в) max ( min ( a₁ , a_2n ) , min ( a₃ , a_2n-2) , . . . , min ( a_2n-1 , a₂ ) ) .
Algoritmi:
1. Tozalangan sonlarni sort qilamiz.
- O(n*log(n)) vaqt talab qiladi.

2. Ikki xonali indeksli dan (a[1] va a[2]-ga) boshlab, o'rta indexcha xa xonali indexli (a[n-1] va a[n]-ga) qadar kamayish tartibida aynan yalpi yagona oraliqdan uzilgunga yarimix birlashgan minlarni hisoblaymiz va ulardan minimumni hisoblaymiz.

- Har bir tartiblanadigan minimalar (yangiMassiv va yalpiMassivning siziga yarimix birlashgan versionlar) bo'yicha O(n/2) ta muvaffaqiyatli harakat talab qiladi.

3. Olchamli qaror qabul qilish orqali, max(n,n/2)-ta shartlar sizish yo'l qo'yadi.

To'plamning eng katta qiymatini topish uchun, ikkita minimalar izlanishi kerak:
- a1 va a2n ko'rinishidagi to'plamlar.
- a3 va a2n-2 ko'rinishidagi to'plamlar.
- ...
- a2n-1 va a2 ko'rinishidagi to'plamlar.

Step 2da, biz o'rta indexchani topish uchun ishlatilgan vaqtalarni jalb qiladigan amalga oshirilgan vaqtimizni boshqarishimiz mumkin.

- O(n/2), ishlatilgan to'plamlarning soni bo'lgan martta.

Shu sabablarga ko'ra, uchta qadamlik algoritmimiz quyidagina ko'rinishda bo'ladi:

```
def max_min(a: List[int], n: int) -> int:
a.sort()
min_val = a[0] + a[2*n-1] # a[1] va a[2n]-ni yig'indisini hisoblaymiz
for i in range(1, n):
min_val = min(min_val, a[i] + a[2*n-i-1]) # Katta tartiblanadigan ildizlarni hisoblash
return min_val
```

Asosiy qiymatlarga yaqinroq kelishni kuzatishdan, ushbu kodega O(n*log(n)) tartibida ishlov beradigan sort() tizimidan boshqa amalga oshirilgan har qanday katta vaqt sarflamaydigan jarayonlar yo'q. Shuningdek, yuqorida ko'rib chiqdigan holda, eng katta tartiblanadigan muvaffaqiyatli harakatlargacha O(n/2) ni hisoblash talab qiladi. Shunga qaramay, umuman funksiyamiz O(n*log(n)) vaqt talab qiladi.