پیچیدگی مجانبی و نرخ رشد
Asymptotic Complexity and Growth Rates
مباحث پیچیدگی مجانبی و نرخهای رشد.
طراحی الگوریتم کنکور ارشد علوم کامپیوتر
کارتها · 13
Adding terms of lower-or-equal order keeps Theta; the largest term dominates, and identities can break when f is not assumed to grow.
An algorithm cannot run faster than the size of the output it must produce, so enumerating exponentially many objects takes exponential time.
Each element of an n-set sits in exactly 2^(n-1) subsets, so the total of all subset-sums is 2^(n-1) times the element sum.
When the argument shrinks by a constant (n-1) instead of a factor, unroll the recurrence; a branching factor a>1 gives exponential growth Θ(a^n) .
A worst-case upper bound ("runs in at most ...") limits the slowest run but says nothing about average case or behavior on a specific input.
For an NP-hard optimization problem, a polynomial-time rho-approximation guarantees a solution within a factor rho of the optimum; the ratio is a monotone worst-case bound (factor c gives every c' >= c for free) and is defined only for optimization, never for decision, problems.
Find the order of the VALUE a loop prints — not its running time — by turning the nested loops into a closed-form sum or product and reading off its leading power.
Checking whether a claimed list of probes is the exact sequence a binary search would make costs only Θ(n) — replay the deterministic search and compare, never re-sort or re-search.
To rank functions slowest-to-fastest, first unmask the impostors: rewrite each as a power of 2 via n=2^(log n) . Some "functions" are secretly constants, and log^()n grows slower than any iterated logarithm.
The cost of a loop is the SUM of the work each iteration does, not (iterations) x (max cost). When the body costs a constant, the sum collapses to (count) x O(1); when the body cost varies with i, evaluate the series. Split a loop with several statements into separate sums and add them.
The cost of a single counted loop is set by how the counter is UPDATED, not how it is compared. Solve the recurrence on the counter, set it equal to the bound n, and invert: i+=c gives n/c steps, i=c gives log_c n steps, and i=ii gives log log n steps.
When the recurrence feeds its own output back into itself, like G(n)=n-G(G(n-1)), unroll a few terms and look for a golden-ratio floor closed form.
A sorted array cyclically rotated by some unknown amount still hides enough order to binary-search it in Θ(log n) : there is exactly one "drop" where A[i]>A[i+1] , and at every midpoint one half is guaranteed sorted, so you can find the pivot, the minimum, the maximum, or any target in logarithmic time.