Efektyvumas
Puiku! Sukursiu praktinį veiklų rinkinį, kurį galima naudoti pamokoje arba savarankiškam mokymuisi. Tai apims duomenų generavimą, algoritmų įgyvendinimą, vykdymo laiko matavimą ir rezultatų analizę.
---
- **Praktinis veiklų rinkinys: Algoritmų efektyvumo tyrimas**
---
- **1. Tikslas**
- Suprasti linijinės ir dvejetainės paieškos efektyvumo skirtumus. - Pamatyti, kaip algoritmų vykdymo laikas kinta, kai masyvas tampa didesnis. - Eksperimentuoti su rikiavimo algoritmais.
---
- **2. Reikalingos priemonės**
- Kompiuteris su įdiegta programavimo aplinka (pvz., Python arba C++). - Python naudotojams: `time` ir `random` moduliai (jau įdiegti).
---
- **3. Užduotys**
---
- **Užduotis 1: Linijinės ir dvejetainės paieškos vykdymo laiko matavimas**
1. **Duomenų generavimas:**
Sugeneruokite atsitiktinį masyvą su 1 000 000 elementų (Python pavyzdys): ```python import random data = [random.randint(1, 1000000) for _ in range(1000000)] data.sort() # Surikiuotas masyvas, skirtas dvejetinei paieškai target = data[len(data) // 2] # Ieškosime vidurinės reikšmės ```
2. **Linijinės paieškos algoritmas:**
Sukurkite funkciją:
```python
def linear_search(arr, target):
for i in range(len(arr)):
if arr[i] == target:
return i
return -1
```
3. **Dvejetinės paieškos algoritmas:**
Sukurkite funkciją:
```python
def binary_search(arr, target):
left, right = 0, len(arr) - 1
while left <= right:
mid = (left + right) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1
```
4. **Vykdymo laiko matavimas:**
Pamatuokite laiką abiem algoritmams: ```python import time
start = time.time()
linear_search(data, target)
end = time.time()
print(f"Linijinė paieška: {end - start:.5f} s")
start = time.time()
binary_search(data, target)
end = time.time()
print(f"Dvejetainė paieška: {end - start:.5f} s")
```
---
- **Užduotis 2: Paieškos efektyvumas esant skirtingiems masyvo dydžiams**
1. **Eksperimentas:**
Sugeneruokite masyvus su 10 000, 100 000 ir 1 000 000 elementų. Naudokite tuos pačius algoritmus, kaip Užduotyje 1.
2. **Analizė:**
Užrašykite rezultatus lentelėje, pavyzdžiui:
| Elementų skaičius | Linijinės paieškos laikas (s) | Dvejetinės paieškos laikas (s) | |-------------------|-----------------------------|------------------------------| | 10 000 | 0.005 | 0.0002 | | 100 000 | 0.05 | 0.0005 | | 1 000 000 | 0.5 | 0.001 |
---
- **Užduotis 3: Rikiavimo algoritmų palyginimas**
1. **Bubble Sort algoritmas:**
Rikiuokite 10 000 elementų masyvą:
```python
def bubble_sort(arr):
n = len(arr)
for i in range(n):
for j in range(0, n-i-1):
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]
```
2. **Built-in rikiavimo funkcija:**
Naudokite Python `sort()` funkciją, kuri naudoja „TimSort“ algoritmą (sudėtingumas: \(O(n \log n)\)).
3. **Vykdymo laiko matavimas:**
Pamatuokite abu algoritmus ir palyginkite: ```python data = [random.randint(1, 100000) for _ in range(10000)]
start = time.time()
bubble_sort(data.copy())
end = time.time()
print(f"Bubble Sort: {end - start:.5f} s")
start = time.time()
data.sort()
end = time.time()
print(f"Built-in Sort: {end - start:.5f} s")
```
4. **Rezultatų analizė:**
Užrašykite skirtumus tarp rikiavimo metodų.
---
- **Papildomos užduotys mokiniams**
1. Sukurkite grafikus, kurie vaizduoja algoritmų vykdymo laiką pagal masyvo dydį (naudodami Python biblioteką `matplotlib`). 2. Modifikuokite dvejetinės paieškos algoritmą taip, kad jis naudotų rekursiją. 3. Diskutuokite, kaip rikiavimas ir paieška yra naudojami realiuose projektuose (pvz., Google paieškos sistema).
---
Ar reikėtų pateikti paruoštą failą su šiuo kodu? Ar norėtumėte gauti rezultatų demonstraciją? 😊