На третьей неделе курса информатики по Python мы углубляемся в основы алгоритмов, понятий эффективности программ и времени выполнения. Также рассматриваются линейный и бинарный поиск, сортировки, а также понятие сложности алгоритма.
Алгоритм — это конечная последовательность действий, направленных на решение задачи. В программировании важно, чтобы алгоритм был эффективным — выполнялся быстро и с минимальными затратами памяти.
Асимптотическая сложность описывает, как время выполнения алгоритма зависит от размера входных данных.
Примеры:
- O(1) — постоянное время;
- O(n) — линейное время;
- O(log n) — логарифмическое время (например, бинарный поиск);
- O(n²) — квадратичное (медленно растёт).
Простой способ найти элемент в списке:
```python```
def linear_search(arr, target):
for i in range(len(arr)):
if arr[i] == target:
return i
return -1
Сложность: O(n)
Бинарный поиск работает только в отсортированных массивах:
```python```
def binary_search(arr, target):
low = 0
high = len(arr) – 1
while low <= high:
mid = (low + high) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
low = mid + 1
else:
high = mid – 1
return -1
Сложность: O(log n)
Наивный метод сортировки:
```python```
def bubble_sort(arr):
for i in range(len(arr)):
for j in range(len(arr) - i - 1):
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
Сложность: O(n²)
Сортировка выбором:
```python```
def selection_sort(arr):
for i in range(len(arr)):
min_idx = i
for j in range(i+1, len(arr)):
if arr[j] < arr[min_idx]:
min_idx = j
arr[i], arr[min_idx] = arr[min_idx], arr[i]
Сортировка вставками:
```python```
def insertion_sort(arr):
for i in range(1, len(arr)):
key = arr[i]
j = i – 1
while j >= 0 and arr[j] > key:
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = key
1. Реализуйте линейный и бинарный поиск.
2. Сравните время выполнения пузырьковой и сортировки вставками.
3. Напишите функцию, которая определяет, является ли массив отсортированным.