TCS: Time Complexity

Time Complexity

Running Time Depends on the Model

Computability asks whether an algorithm eventually returns the correct answer. Complexity also counts the resources required before it does so

For a deterministic machine $M$ that halts on every input, define its worst-case running time by

T_M(n)=\max_{|x|=n}\operatorname{steps}_M(x)

The maximum gives a guarantee for every input of that size. An average-case bound would additionally require a distribution over inputs

Palindromes

On a single tape, one algorithm compares the leftmost and rightmost remaining symbols, marks them, and repeats. Each comparison can require a sweep across most of the input, giving

T(n)=\Theta(n+(n-2)+(n-4)+\cdots)=\Theta(n^2)

A two-tape machine can copy the input and compare opposite traversals in $O(n)$ time. A RAM algorithm with constant-time indexed access can similarly use two indices

The quadratic cost belongs to the single-tape model, rather than to the abstract palindrome problem under every model. For the standard one-tape model, a matching quadratic worst-case lower bound can be proved using crossing sequences

RAM and Bit Costs

A RAM machine provides indexed memory and operations on registers. In a word-RAM analysis, a word commonly contains $\Theta(\log n)$ bits and the supported word operations have unit cost

An operation on an arbitrarily long integer cannot automatically be treated as one constant-time step. The input encoding and the sizes of intermediate values are part of a complexity analysis

Reasonable classical models with appropriate bit or word costs simulate one another with polynomial overhead, even when their precise running times differ

Asymptotic Notation

For eventually nonnegative functions $f,g$ ,

\begin{aligned}f(n)=O(g(n))&\iff\exists c>0\ \exists n_0\ \forall n\ge n_0:f(n)\le cg(n)\\f(n)=\Omega(g(n))&\iff\exists c>0\ \exists n_0\ \forall n\ge n_0:f(n)\ge cg(n)\end{aligned}

The notation $f(n)=\Theta(g(n))$ asserts both bounds, while $f(n)=o(g(n))$ means $f(n)/g(n)\to0$ when $g$ is eventually positive

Thus $7n^2+3n+8$ is $\Theta(n^2)$ and also $O(n^3)$ , but the latter loses information about its actual growth

A useful ordering is

\log n\ll n\ll n\log n\ll n^2\ll2^n\ll n!

The comparison concerns sufficiently large inputs. Constants and lower-order terms still affect practical performance

Recurrences

Divide-and-conquer algorithms often lead to

T(n)=aT(n/b)+f(n)

For binary search, one branch survives and the work per level is constant, so $T(n)=T(n/2)+O(1)=O(\log n)$

For merge sort, the total merging work at each level is $\Theta(n)$ and there are $\Theta(\log n)$ levels, giving $T(n)=\Theta(n\log n)$

Algorithms, Problems and Complexity Classes

An algorithm provides an upper bound for a problem. A lower bound must apply to every algorithm in the chosen model

For example, a palindrome algorithm must inspect linearly many input symbols in the worst case: on an all-zero string, leaving an off-center position unread allows an adversary to change it and create a non-palindrome without changing the observed computation

One should not assume that every problem has a fastest algorithm with a tight $\Theta$ bound. Complexity classes let us state resource bounds without needing such an optimal algorithm

\operatorname{TIME}(t(n))=\{L:L\text{ has a deterministic decider using }O(t(n))\text{ time}\}

For a fixed standard Turing-machine model, define

\begin{aligned}\mathrm P&=\bigcup_{k\ge1}\operatorname{TIME}(n^k)\\\mathrm{EXP}&=\bigcup_{k\ge1}\operatorname{TIME}(2^{n^k})\end{aligned}

Polynomial bounds are closed under composition, addition and multiplication. This makes $\mathrm P$ stable under polynomial-time preprocessing and changes between polynomially equivalent computational models

A polynomial algorithm may still be impractical if its exponent is large. Membership in $\mathrm P$ is a mathematical criterion of efficiency, with finer algorithmic analysis needed for actual implementations

The Deterministic Time Hierarchy

An unlimited diagonalization proves undecidability. A time-bounded diagonalization instead constructs a decidable language that cannot be decided with a smaller time budget

Time Constructibility

A time bound is time-constructible when a machine can implement the corresponding clock within that order of time. Standard polynomial and exponential bounds satisfy the required regularity conditions

This requirement allows the diagonal machine to stop its simulation according to its own resource budget

For suitable time-constructible bounds $t_1,t_2$ with $t_1(n)\ge n$ , the standard multitape deterministic time hierarchy theorem gives

t_1(n)\log t_1(n)=o(t_2(n))\quad\Longrightarrow\quad\operatorname{TIME}(t_1(n))\subsetneq\operatorname{TIME}(t_2(n))

The logarithmic allowance accommodates efficient universal simulation in this model

Diagonalization with a Clock

The proof enumerates programs together with clocks. On an input encoding a program, the diagonal machine simulates that program on the same input for a prescribed number of steps and reverses its answer if the simulation finishes

Padding the encoding gives arbitrarily long inputs describing the same program. This ensures the contradiction occurs beyond any fixed threshold hidden in an asymptotic running-time bound

If a smaller-time decider computed the diagonal language, a sufficiently long padded description of that decider would make the diagonal machine disagree with it. The clock keeps the diagonal machine itself within the larger bound

In particular, for constants $1\le a<b$ ,

\operatorname{TIME}(n^a)\subsetneq\operatorname{TIME}(n^b) \qquad \mathrm P\subsetneq\mathrm{EXP}

The second separation follows by choosing a single sufficiently large exponential time bound that dominates the simulation of every fixed polynomial-time machine

Why the Regularity Condition Matters

The gap theorem shows that arbitrary computable bounds can behave very differently: there exists an increasing computable $g$ such that

\operatorname{TIME}(g(n)) =\operatorname{TIME}(2^{g(n)})

Such a bound can be constructed to avoid the running times of successively more machines over large intervals. It need not be efficiently constructible, so the clock required by the hierarchy argument is unavailable

The hierarchy theorem guarantees the existence of hard decidable languages. It does not identify SAT or any other particular natural problem as requiring superpolynomial time

本文采用署名-非商业性使用-相同方式共享 4.0 国际许可协议，转载请注明出处。