Complessità computazionale

Ricorrenze e teorema master

T(n) = 4 T(ⁿ/₂) + na = 4   b = 2   β = 1α = 2   β = 1,   α > βα = log_b(a) = log₂ 4 = 2T(n) = O(n^α)

T(n) = 4 T(ⁿ/₂) + n²a = 4   b = 2,   α = log₂ 4 = 2   β = 2,   α = βT(n) = O(n² log₂ n)

T(n) = 4 T(ⁿ/₂) + ⁿ²/_{log n}T(n) = 4 (4 T(ⁿ/₄) + (ⁿ²/_log(ⁿ/2)) + ⁿ²/_{log n}= 16 T(ⁿ/₄) + 4 ⁿ²/_log(ⁿ/2) + ⁿ²/_{log n}= 16 T(ⁿ/₄) + ⁿ²/_log(n/2) + ⁿ²/_log(n)= 2^2k T(ⁿ/_2^k) + n² Σ_i=0^K-1 1 / log_b(ⁿ/_2ⁱ)n / 2^k = 1   n = 2^k   K = log n

Esempi di ricorrenze

1. T(n) = 4T(ⁿ⁄₂) + na = 4   b = 2   β = 1α = log_b(a) = 2d > βT(n) = O(n^d)
2. T(n) = 4T(ⁿ⁄₂) + n²a = 4   b = 2α = log₂ a = 2β = 2   α = βT(n) = O(n² log₂ n)
3. T(n) = 4T(n⁄2) + n2⁄log nT(n) = 4 (4 T(n⁄4) + n2⁄log(n⁄2) + n2⁄log n)= 16 T(n⁄4) + 4 n2⁄log(n⁄2) + n2⁄log n= 16 T(n⁄4) + n2⁄log(n⁄2) + n2⁄log(n)= 22k T(n⁄2k) + n2 k-1n2k = 1   n = 2kK = log nq = 2log n= n2 + n2 k-1∑i=0 1/log n - log 2i= n2 + n2 ∑k-log 2i 1= n2 + n2 ∑k-i 1O(n2 log k) = O(n2 log log n)
4. T(n) = 7 T(ⁿ/₂) + n²a = 7 b = 2 d = log_b a = log₂ 7 β = 2d > βT(n) = O(n^{log₂ 7})

Ricorrenza T'(n)

T'(n) = a T'(ⁿ/_a) + n²T'(n) = O(n^{log₂ a})a = f - εlog₂ 7 = log₄ 49T'(n) = ?log₄a²n log₄a² ? n²log₄a = 2 a = 16n log₄a² < n²n log₄a² = n²se a < 16: T'(n) = Θ(n²)se a = 16: T'(n) = n²log nse a > 16: T'(n) = O(n log₄a²)

Espansione della ricorrenza

T(n) = 2 T(n/2) + O(n) T(1) = O(1)

T(n) = 2(2 T(n / 4) + O(n / 2)) + O(n)= 4 T(n / 4) + 2 O(n / 2) + O(n)= 2^k T(n / 2^k) + 2 O(n / 2) + 2 O(n / 2⁰)= n / 2^k = 1 n = 2^k k = log₂n= 2^k T(n / 2^k) + ∑_ℓ=0^k-12^ℓ O(n / 2^ℓ)k = log₂n= 2_log2nT(1) + ^{log₂n - 1} ∑_i=02ⁱO(ⁿ/_2ⁱ)= 2_log2n(O(1) + n ∑ O(²ⁱ/_2ⁱ))= 2_log2n(O(1) + n ∑_i=0^{log₂n - 1} O(1))= n O(1) + n O(log n)= O(n) + O(n log n) = O(n log n)

Seconda espansione

2) T(n) = 3 T(ⁿ/₂) + O(n) T(1) = O(1)

T(n) = 3(3 T(ⁿ/₄) + O(ⁿ/₂)) + O(n)= 3 T(ⁿ/₄) + 3 O(ⁿ/₂) + O(n)= 3^kT(ⁿ/_2^k) + 3 O(ⁿ/₂) + O(n)=...3^kT(ⁿ/_2^k) + ^k-1∑_i=03ⁱO(ⁿ/_2ⁱ)k = log₂n= 3^log₂nO(1) + ∑_{i = 0}^{log₂h - 1}3ⁱO(b_i/2ⁱ)= 3^log₂nO(1 + h∑_{i = 0}^{log₂h - 1}O(3ⁱ/2ⁱ))

3^log₂n = 3 = 3^log₃n = n^log₃3= O(n^log₂3) + n ∑ O(3ⁱ/2ⁱ)∑_{i = 0}^log_n-1(3/2)ⁱ = (3/2)^log₂n - 1/3/2 - 1 = 2((3/2)^log₂n - 1)(3/2)^log₂n = 3^log₃n/2^log₂n = n/hO(n^log₃1) = O(n^log₂3)= O(n^log₂3) + O(n^log₃3) = O(n^log₃3)

T(n) = aT(n/b) + na = 9   b = 3   d = log₃a = 2   β = 1d > β   T(n) = O(n²)