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ę.

---

1. 1. 1. **Praktinis veiklų rinkinys: Algoritmų efektyvumo tyrimas**

---

1. 1. 1. 1. **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.

---

1. 1. 1. 1. **2. Reikalingos priemonės**

- Kompiuteris su įdiegta programavimo aplinka (pvz., Python arba C++). - Python naudotojams: `time` ir `random` moduliai (jau įdiegti).

---

1. 1. 1. 1. **3. Užduotys**

---

1. 1. 1. **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")
  ```

---

1. 1. 1. **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                        |

---

1. 1. 1. **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ų.

---

1. 1. 1. **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ą? 😊