Böl ve Fethet

package main

import (
	"fmt"
	"math"
)

// masterTheorem: a, b ve f(n)'in derecesi verildiğinde sonucu belirler
func masterTheorem(a, b int, fDegree float64) (string, string) {
	critical := math.Log(float64(a)) / math.Log(float64(b))

	const eps = 1e-9
	switch {
	case fDegree < critical-eps:
		return "Durum 1", fmt.Sprintf("Θ(n^%.2f)", critical)
	case math.Abs(fDegree-critical) < eps:
		return "Durum 2", fmt.Sprintf("Θ(n^%.2f · log n)", critical)
	default:
		return "Durum 3", fmt.Sprintf("Θ(n^%.2f)", fDegree)
	}
}

func main() {
	examples := []struct {
		name    string
		a, b    int
		fDegree float64
	}{
		{"ikili arama: T(n)=T(n/2)+O(1)", 1, 2, 0},
		{"birleştirmeli: T(n)=2T(n/2)+O(n)", 2, 2, 1},
		{"Karatsuba: T(n)=3T(n/2)+O(n)", 3, 2, 1},
		{"matris çarpımı: T(n)=8T(n/2)+O(n²)", 8, 2, 2},
		{"Strassen: T(n)=7T(n/2)+O(n²)", 7, 2, 2},
		{"ağaç yüksekliği: T(n)=2T(n/2)+O(1)", 2, 2, 0},
		{"pahalı birleştirme: T(n)=2T(n/2)+O(n²)", 2, 2, 2},
	}

	fmt.Printf("%-38s %10s %22s\n", "bağıntı", "durum", "sonuç")
	for _, e := range examples {
		durum, sonuc := masterTheorem(e.a, e.b, e.fDegree)
		fmt.Printf("%-38s %10s %22s\n", e.name, durum, sonuc)
	}

	fmt.Println()
	fmt.Println("Kritik büyüklük n^(log_b a) ile f(n)'i karşılaştırırız:")
	fmt.Println("  f küçükse → alt problemler baskın")
	fmt.Println("  eşitse    → her seviye eşit iş, log n çarpanı eklenir")
	fmt.Println("  f büyükse → birleştirme baskın")
}

package main

import "fmt"

var multiplications int

// powNaive: O(n)
func powNaive(a, n int) int {
	result := 1
	for range n {
		result *= a
		multiplications++
	}
	return result
}

// powFast: O(log n) — böl ve fethet
func powFast(a, n int) int {
	if n == 0 {
		return 1
	}
	half := powFast(a, n/2)
	multiplications++
	result := half * half
	if n%2 == 1 {
		multiplications++
		result *= a
	}
	return result
}

// powIterative: aynı fikrin döngü hâli (bitlere bakar)
func powIterative(a, n int) int {
	result := 1
	for n > 0 {
		if n&1 == 1 {
			result *= a
			multiplications++
		}
		a *= a
		multiplications++
		n >>= 1
	}
	return result
}

// powMod: modüler üs alma — kriptografinin temel işlemi
func powMod(a, n, mod int) int {
	result := 1
	a %= mod
	for n > 0 {
		if n&1 == 1 {
			result = result * a % mod
		}
		a = a * a % mod
		n >>= 1
	}
	return result
}

func main() {
	fmt.Printf("%6s %14s %10s %14s %10s\n", "n", "naif sonuç", "çarpma", "hızlı sonuç", "çarpma")
	for _, n := range []int{1, 5, 10, 20, 30} {
		multiplications = 0
		naive := powNaive(2, n)
		naiveMults := multiplications

		multiplications = 0
		fast := powFast(2, n)
		fastMults := multiplications

		fmt.Printf("%6d %14d %10d %14d %10d\n", n, naive, naiveMults, fast, fastMults)
	}

	fmt.Println()
	multiplications = 0
	fmt.Println("3^13 iteratif =", powIterative(3, 13), "| çarpma:", multiplications)

	fmt.Println()
	fmt.Println("modüler üs alma (RSA'nın temeli):")
	fmt.Println("  7^128 mod 13 =", powMod(7, 128, 13))
	fmt.Println("  2^1000 mod 1_000_000_007 =", powMod(2, 1000, 1_000_000_007))
	fmt.Println("→ naif yöntemle 2^1000 hesaplamak taşma yaratırdı")
}

package main

import (
	"fmt"
	"math/rand/v2"
	"slices"
)

var partitions int

func partition(data []int, lo, hi int) int {
	partitions++
	pivot := data[hi]
	i := lo
	for j := lo; j < hi; j++ {
		if data[j] < pivot {
			data[i], data[j] = data[j], data[i]
			i++
		}
	}
	data[i], data[hi] = data[hi], data[i]
	return i
}

// quickselect: k. en küçük eleman (1 tabanlı) — beklenen O(n)
func quickselect(data []int, k int, r *rand.Rand) (int, bool) {
	if k < 1 || k > len(data) {
		return 0, false
	}
	work := slices.Clone(data)
	target := k - 1
	lo, hi := 0, len(work)-1

	for lo <= hi {
		// Rastgele pivot: en kötü durumu pratikte imkânsız kılar
		pick := lo + r.IntN(hi-lo+1)
		work[pick], work[hi] = work[hi], work[pick]

		p := partition(work, lo, hi)
		switch {
		case p == target:
			return work[p], true
		case p < target:
			lo = p + 1 // sağ tarafa in
		default:
			hi = p - 1 // sol tarafa in
		}
	}
	return 0, false
}

// median: ortanca değer
func median(data []int, r *rand.Rand) float64 {
	n := len(data)
	if n == 0 {
		return 0
	}
	if n%2 == 1 {
		v, _ := quickselect(data, n/2+1, r)
		return float64(v)
	}
	a, _ := quickselect(data, n/2, r)
	b, _ := quickselect(data, n/2+1, r)
	return float64(a+b) / 2
}

// topK: en büyük k eleman
func topK(data []int, k int, r *rand.Rand) []int {
	if k >= len(data) {
		out := slices.Clone(data)
		slices.Sort(out)
		return out
	}
	threshold, _ := quickselect(data, len(data)-k+1, r)
	var out []int
	for _, v := range data {
		if v >= threshold {
			out = append(out, v)
		}
	}
	slices.Sort(out)
	return out[max(0, len(out)-k):]
}

func main() {
	r := rand.New(rand.NewPCG(3, 7))
	data := []int{7, 2, 9, 1, 5, 3, 8, 6, 4}

	fmt.Println("dizi:", data)
	sorted := slices.Clone(data)
	slices.Sort(sorted)
	fmt.Println("sıralı hâli:", sorted)
	fmt.Println()

	for k := 1; k <= len(data); k++ {
		partitions = 0
		v, _ := quickselect(data, k, r)
		fmt.Printf("  %d. en küçük = %-3d (sıralıdaki: %-3d doğru: %-5t bölümleme: %d)\n",
			k, v, sorted[k-1], v == sorted[k-1], partitions)
	}

	fmt.Println()
	fmt.Println("ortanca:", median(data, r))
	fmt.Println("en büyük 3:", topK(data, 3, r))

	// Büyük dizide karşılaştırma
	fmt.Println()
	const n = 10_000
	big := make([]int, n)
	for i := range big {
		big[i] = r.IntN(100_000)
	}
	partitions = 0
	v, _ := quickselect(big, n/2, r)
	selectParts := partitions

	bigSorted := slices.Clone(big)
	slices.Sort(bigSorted)

	fmt.Printf("n=%d için ortanca bulma:\n", n)
	fmt.Println("  quickselect sonucu:", v, "doğru mu:", v == bigSorted[n/2-1])
	fmt.Println("  quickselect bölümleme sayısı:", selectParts)
	fmt.Println("  sıralama yapsaydık ~n log n =", n*14, "karşılaştırma gerekirdi")
}

package main

import "fmt"

// maxCrossing: ortadan geçen en iyi alt diziyi bulur — O(n)
func maxCrossing(data []int, lo, mid, hi int) int {
	leftBest, sum := -1<<62, 0
	for i := mid; i >= lo; i-- {
		sum += data[i]
		leftBest = max(leftBest, sum)
	}

	rightBest, sum := -1<<62, 0
	for i := mid + 1; i <= hi; i++ {
		sum += data[i]
		rightBest = max(rightBest, sum)
	}
	return leftBest + rightBest
}

// maxSubarrayDC: böl ve fethet — O(n log n)
func maxSubarrayDC(data []int, lo, hi int) int {
	if lo == hi {
		return data[lo]
	}
	mid := lo + (hi-lo)/2
	return max(
		maxSubarrayDC(data, lo, mid),
		maxSubarrayDC(data, mid+1, hi),
		maxCrossing(data, lo, mid, hi),
	)
}

// kadane: dinamik programlama — O(n), çok daha basit
func kadane(data []int) (best, start, end int) {
	if len(data) == 0 {
		return 0, -1, -1
	}
	best, current := data[0], data[0]
	start, end, tempStart := 0, 0, 0

	for i := 1; i < len(data); i++ {
		if current < 0 {
			current = data[i] // geçmişi at, buradan başla
			tempStart = i
		} else {
			current += data[i]
		}
		if current > best {
			best, start, end = current, tempStart, i
		}
	}
	return best, start, end
}

func main() {
	cases := [][]int{
		{-2, 1, -3, 4, -1, 2, 1, -5, 4},
		{1, 2, 3, 4, 5},
		{-5, -2, -8, -1},
		{5, -3, 5},
		{42},
	}

	fmt.Printf("%-32s %10s %10s %8s %-18s\n", "dizi", "böl-fethet", "Kadane", "aynı", "en iyi aralık")
	for _, c := range cases {
		dc := maxSubarrayDC(c, 0, len(c)-1)
		k, start, end := kadane(c)
		fmt.Printf("%-32v %10d %10d %8t %-18v\n", c, dc, k, dc == k, c[start:end+1])
	}

	fmt.Println()
	fmt.Println("Böl ve fethet: O(n log n) — öğretici ama optimal değil")
	fmt.Println("Kadane algoritması: O(n) — dinamik programlama yaklaşımı")
}

package main

import (
	"fmt"
	"slices"
)

// mergeCount: birleştirirken ters çevrim sayar
func mergeCount(data, buf []int, lo, mid, hi int) int {
	i, j, k := lo, mid, lo
	inversions := 0

	for i < mid && j < hi {
		if data[i] <= data[j] {
			buf[k] = data[i]
			i++
		} else {
			buf[k] = data[j]
			j++
			inversions += mid - i // sol dizide kalan her eleman bir ters çevrim
		}
		k++
	}
	for i < mid {
		buf[k] = data[i]
		i, k = i+1, k+1
	}
	for j < hi {
		buf[k] = data[j]
		j, k = j+1, k+1
	}
	copy(data[lo:hi], buf[lo:hi])
	return inversions
}

// countInversions: O(n log n)
func countInversions(data []int) int {
	work := slices.Clone(data)
	buf := make([]int, len(work))

	var sort func(lo, hi int) int
	sort = func(lo, hi int) int {
		if hi-lo <= 1 {
			return 0
		}
		mid := lo + (hi-lo)/2
		count := sort(lo, mid) + sort(mid, hi)
		return count + mergeCount(work, buf, lo, mid, hi)
	}
	return sort(0, len(work))
}

// bruteForce: O(n²)
func bruteForce(data []int) int {
	count := 0
	for i := range data {
		for j := i + 1; j < len(data); j++ {
			if data[i] > data[j] {
				count++
			}
		}
	}
	return count
}

func main() {
	cases := [][]int{
		{1, 2, 3, 4, 5}, // sıralı: 0
		{5, 4, 3, 2, 1}, // ters: n(n-1)/2 = 10
		{2, 4, 1, 3, 5}, // karışık
		{1, 3, 2, 3, 1}, // tekrarlı
		{7},             // tek
		{},              // boş
	}

	fmt.Printf("%-24s %14s %14s %8s\n", "dizi", "böl-fethet", "kaba kuvvet", "aynı")
	for _, c := range cases {
		fast := countInversions(c)
		slow := bruteForce(c)
		fmt.Printf("%-24v %14d %14d %8t\n", c, fast, slow, fast == slow)
	}

	// Büyük dizide fark
	fmt.Println()
	const n = 2000
	descending := make([]int, n)
	for i := range descending {
		descending[i] = n - i
	}
	fmt.Printf("n=%d ters sıralı dizi:\n", n)
	fmt.Println("  ters çevrim sayısı:", countInversions(descending))
	fmt.Println("  teorik maksimum n(n-1)/2 =", n*(n-1)/2)
	fmt.Println("  böl-fethet ~n log n =", n*11, "işlem")
	fmt.Println("  kaba kuvvet n² =", n*n, "işlem")
}