Böl ve Yönet, Algoritma Tasarımı ve Analizi

T = aT(n/b) + f burada:
            T, n boyutundaki bir problem için zaman karmaşıklığıdır.
            a alt problemlerin sayısıdır.
            n/b her bir alt problemin boyutudur.
            f özyinelemeli çağrıların dışındaki maliyettir (örneğin, çözümlerin birleştirilmesi).

T = aT(n/b) + f

Ana Teorem, f fonksiyonunun n^log_b(a) ile karşılaştırılmasını içerir, burada

    a yinelemedeki alt problemlerin sayısıdır.
    b, problem boyutunun bölündüğü faktördür.
    f özyinelemeli çağrıların dışındaki maliyettir.

Durum 1: Eğer f = O(n^c) ise ve burada c < log_b(a) ise, o zaman:
        T = Θ(n^log_b(a))

    Durum 2: Eğer f = Θ(n^c) ise, burada c = log_b(a), o zaman:
        T = Θ(n^c * log^k) burada k >= 0

    Durum 3: Eğer f = Ω(n^c) ise, burada c > log_b(a) ise ve bazı k < 1 için a f(n/b) <= k f ise, o zaman:
        T = Θ(f)

Yineleme Bağıntısı: T = 2T(n/2) + O
    Ana Teoremin Uygulanması:
        Burada, a = 2, b = 2 ve f = O.
        log_b(a) = log_2(2) = 1 olarak hesaplayın.
        f ile n^log_b(a)'yı karşılaştırın: f = O ve n^log_b(a) = n^1.
        Ana Teorem'in 2. Durumuna göre, f = Θ(n^c) olduğundan ve burada c = log_b(a) olduğundan, zaman karmaşıklığı
        T = Θ(n * log^k) burada k >= 0'dır, bu da Θ(n log n)'ye basitleştirir.

Yineleme Bağıntısı: T = T(n/2) + O(1)
    Ana Teoremin Uygulanması:
        Burada, a = 1, b = 2 ve f = O(1)'dir.
        log_b(a) = log_2(1) = 0 olarak hesaplayın.
        f ile n^log_b(a)'yı karşılaştırın: f = O(1) ve n^log_b(a) = n^0.
        Ana Teorem'in 1. Durumuna göre, f = O(n^c) olduğundan ve burada c < log_b(a) olduğundan, zaman karmaşıklığı
        T = Θ(n^log_b(a)), bu da Θ(log n)'ye basitleştirir.

def binary_search(arr, target):
    low, high = 0, 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

# Testing binary search
arr = [1, 3, 5, 7, 9, 11]
target = 7
index = binary_search(arr, target)
print(f"Index of {target} in the array is: {index}")

def merge_sort(arr):
    if len(arr) <= 1:
        return arr

    mid = len(arr) // 2
    left_half = merge_sort(arr[:mid])
    right_half = merge_sort(arr[mid:])

    return merge(left_half, right_half)

def merge(left, right):
    sorted_arr = []
    i = j = 0

    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            sorted_arr.append(left[i])
            i += 1
        else:
            sorted_arr.append(right[j])
            j += 1

    sorted_arr.extend(left[i:])
    sorted_arr.extend(right[j:])

    return sorted_arr

# Testing merge sort
arr = [38, 27, 43, 3, 9, 82, 10]
sorted_arr = merge_sort(arr)
print("Sorted array:", sorted_arr)

def quick_sort(arr):
    if len(arr) <= 1:
        return arr

    pivot = arr[len(arr) // 2]
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]

    return quick_sort(left) + middle + quick_sort(right)

# Testing quick sort
arr = [33, 10, 59, 27, 46, 81]
sorted_arr = quick_sort(arr)
print("Sorted array:", sorted_arr)

import numpy as np

def add_matrices(A, B):
    return np.add(A, B)

def subtract_matrices(A, B):
    return np.subtract(A, B)

def split_matrix(M):
    n, m = M.shape
    mid_n, mid_m = n // 2, m // 2
    A11 = M[:mid_n, :mid_m]
    A12 = M[:mid_n, mid_m:]
    A21 = M[mid_n:, :mid_m]
    A22 = M[mid_n:, mid_m:]
    return A11, A12, A21, A22

def merge_matrices(C11, C12, C21, C22):
    top = np.hstack((C11, C12))
    bottom = np.hstack((C21, C22))
    return np.vstack((top, bottom))

def brute_force(A, B):
    return np.dot(A, B)

def strassen(A, B):
    if len(A) <= 2:
        return brute_force(A, B)

    a, b, c, d = split_matrix(A)
    e, f, g, h = split_matrix(B)

    p1 = strassen(add_matrices(a, d), add_matrices(e, h))
    p2 = strassen(d, subtract_matrices(g, e))
    p3 = strassen(add_matrices(a, b), h)
    p4 = strassen(b, subtract_matrices(g, h))
    p5 = strassen(a, subtract_matrices(f, h))
    p6 = strassen(add_matrices(c, d), e)
    p7 = strassen(subtract_matrices(a, c), add_matrices(e, f))

    C11 = add_matrices(subtract_matrices(add_matrices(p1, p2), p3), p4)
    C12 = add_matrices(p5, p3)
    C21 = add_matrices(p6, p2)
    C22 = add_matrices(subtract_matrices(add_matrices(p1, p5), p6), p7)

    return merge_matrices(C11, C12, C21, C22)

# Testing Strassen matrix multiplication
A = np.array([[1, 2, 3, 4],
              [5, 6, 7, 8]])

B = np.array([[16, 15, 14],
              [12, 11, 10],
              [8, 7, 6],
              [4, 3, 2]])

C = strassen(A, B)
print("Result of Strassen's matrix multiplication:")
print(C)

def karatsuba(x, y):
    if x < 10 or y < 10:
        return x * y
    else:
        n = max(len(str(x)), len(str(y)))
        half = n // 2
        a = x // (10 ** half)  # left part of x
        b = x % (10 ** half)   # right part of x
        c = y // (10 ** half)  # left part of y
        d = y % (10 ** half)   # right part of y

        ac = karatsuba(a, c)
        bd = karatsuba(b, d)
        ad_plus_bc = karatsuba(a + b, c + d) - ac - bd

        return ac * (10 ** (2 * half)) + (ad_plus_bc * (10 ** half)) + bd

# Testing the method
x = 12476
y = 12343
result = karatsuba(x, y)
print(f"The result of {x} * {y} using Karatsuba algorithm is: {result}")