Movatterモバイル変換

[0]ホーム
URL:

Jump to content
WikipediaThe Free Encyclopedia
Search

Time complexity

From Wikipedia, the free encyclopedia
(Redirected fromConstant time)
Estimate of time taken for running an algorithm
"Running time" redirects here; not to be confused withRunning Time (film).
Graphs of functions commonly used in theanalysis of algorithms, showing the number of operationsN as the result of input sizen for each function

Intheoretical computer science, thetime complexity is thecomputational complexity that describes the amount of computer time it takes to run analgorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by the algorithm, supposing that each elementary operation takes a fixed amount of time to perform. Thus, the amount of time taken and the number of elementary operations performed by the algorithm are taken to be related by aconstant factor.

Since an algorithm's running time may vary among different inputs of the same size, one commonly considers theworst-case time complexity, which is the maximum amount of time required for inputs of a given size. Less common, and usually specified explicitly, is theaverage-case complexity, which is the average of the time taken on inputs of a given size (this makes sense because there are only a finite number of possible inputs of a given size). In both cases, the time complexity is generally expressed as afunction of the size of the input.[1]: 226  Since this function is generally difficult to compute exactly, and the running time for small inputs is usually not consequential, one commonly focuses on the behavior of the complexity when the input size increases—that is, theasymptotic behavior of the complexity. Therefore, the time complexity is commonly expressed usingbig O notation, typicallyO(n){\displaystyle O(n)},O(nlog⁡n){\displaystyle O(n\log n)},O(nα){\displaystyle O(n^{\alpha })},O(2n){\displaystyle O(2^{n})}, etc., wheren is the size in units ofbits needed to represent the input.

Algorithmic complexities are classified according to the type of function appearing in the big O notation. For example, an algorithm with time complexityO(n){\displaystyle O(n)} is alinear time algorithm and an algorithm with time complexityO(nα){\displaystyle O(n^{\alpha })} for some constantα>0{\displaystyle \alpha >0} is apolynomial time algorithm.

Table of common time complexities

[edit]
Further information:Computational complexity of mathematical operations

The following table summarizes some classes of commonly encountered time complexities. In the table,poly(x) =xO(1), i.e., polynomial in x.

NameComplexity classTime complexity(O(n))Examples of running timesExample algorithms
constant timeO(1){\displaystyle O(1)}10Finding the median value in a sortedarray of numbers. Calculating(−1)n.
inverse Ackermann timeO(α(n)){\displaystyle O{\bigl (}\alpha (n){\bigr )}}Amortized time per operation using adisjoint set
iterated logarithmic timeO(log∗⁡n){\displaystyle O(\log ^{*}n)}Distributed coloring of cycles
log-logarithmicO(log⁡log⁡n){\displaystyle O(\log \log n)}Amortized time per operation using a boundedpriority queue[2]
logarithmic timeDLOGTIMEO(log⁡n){\displaystyle O(\log n)}log⁡n{\displaystyle \log n},log⁡(n2){\displaystyle \log(n^{2})}Binary search
polylogarithmic timepoly(log⁡n){\displaystyle {\text{poly}}(\log n)}(log⁡n)2{\displaystyle (\log n)^{2}}
fractional powerO(nc){\displaystyle O(n^{c})} where0<c<1{\displaystyle 0<c<1}n12{\displaystyle n^{\frac {1}{2}}},n23{\displaystyle n^{\frac {2}{3}}}Range searching in ak-d tree
linear timeO(n){\displaystyle O(n)}n,2n+5{\displaystyle 2n+5}Finding the smallest or largest item in an unsortedarray.Kadane's algorithm.Linear search.
"n log-star n" timeO(nlog∗⁡n){\displaystyle O(n\log ^{*}n)}Seidel'spolygon triangulation algorithm.
linearithmic timeO(nlog⁡n){\displaystyle O(n\log n)}nlog⁡n{\displaystyle n\log n},log⁡n!{\displaystyle \log n!}Fastest possiblecomparison sort.Fast Fourier transform.
quasilinear timenpoly(log⁡n){\displaystyle n{\text{poly}}(\log n)}nlog2⁡n{\displaystyle n\log ^{2}n}Multipoint polynomial evaluation
quadratic timeO(n2){\displaystyle O(n^{2})}n2{\displaystyle n^{2}}Bubble sort.Insertion sort.Direct convolution
cubic timeO(n3){\displaystyle O(n^{3})}n3{\displaystyle n^{3}}Naive multiplication of twon×n{\displaystyle n\times n} matrices. Calculatingpartial correlation.
polynomial timeP2O(log⁡n)=poly(n){\displaystyle 2^{O(\log n)}={\text{poly}}(n)}n2+n{\displaystyle n^{2}+n},n10{\displaystyle n^{10}}Karmarkar's algorithm forlinear programming.AKS primality test[3][4]
quasi-polynomial timeQP2poly(log⁡n){\displaystyle 2^{{\text{poly}}(\log n)}}nlog⁡log⁡n{\displaystyle n^{\log \log n}},nlog⁡n{\displaystyle n^{\log n}}Best-knownO(log2n)-approximation algorithm for the directedSteiner tree problem, best knownparity game solver,[5] best knowngraph isomorphism algorithm
sub-exponential time
(first definition)		SUBEXPO(2nϵ){\displaystyle O(2^{n^{\epsilon }})} for all0<ϵ<1{\displaystyle 0<\epsilon <1}ContainsBPP unless EXPTIME (see below) equalsMA.[6]
sub-exponential time
(second definition)		2o(n){\displaystyle 2^{o(n)}}2n3{\displaystyle 2^{\sqrt[{3}]{n}}}Best classical algorithm forinteger factorization

formerly-best algorithm forgraph isomorphism

exponential time
(with linear exponent)		E2O(n){\displaystyle 2^{O(n)}}1.1n{\displaystyle 1.1^{n}},10n{\displaystyle 10^{n}}Solving thetraveling salesman problem usingdynamic programming
factorial timeO(n)!=2O(nlog⁡n){\displaystyle O(n)!=2^{O(n\log n)}}n!,nn,2nlog⁡n{\displaystyle n!,n^{n},2^{n\log n}}Solving thetraveling salesman problem viabrute-force search
exponential timeEXPTIME2poly(n){\displaystyle 2^{{\text{poly}}(n)}}2n{\displaystyle 2^{n}},2n2{\displaystyle 2^{n^{2}}}Solvingmatrix chain multiplication viabrute-force search
double exponential time2-EXPTIME22poly(n){\displaystyle 2^{2^{{\text{poly}}(n)}}}22n{\displaystyle 2^{2^{n}}}Deciding the truth of a given statement inPresburger arithmetic

Constant time

[edit]
"Constant time" redirects here. For programming technique to avoid a timing attack, seeTiming attack § Avoidance.

An algorithm is said to beconstant time (also written asO(1){\textstyle O(1)} time) if the value ofT(n){\textstyle T(n)} (the complexity of the algorithm) is bounded by a value that does not depend on the size of the input. For example, accessing any single element in anarray takes constant time as only oneoperation has to be performed to locate it. In a similar manner, finding the minimal value in an array sorted in ascending order; it is the first element. However, finding the minimal value in an unordered array is not a constant time operation as scanning over eachelement in the array is needed in order to determine the minimal value. Hence it is a linear time operation, takingO(n){\textstyle O(n)} time. If the number of elements is known in advance and does not change, however, such an algorithm can still be said to run in constant time.

Despite the name "constant time", the running time does not have to be independent of the problem size, but an upper bound for the running time has to be independent of the problem size. For example, the task "exchange the values ofa andb if necessary so thata≤b{\textstyle a\leq b}" is called constant time even though the time may depend on whether or not it is already true thata≤b{\textstyle a\leq b}. However, there is some constantt such that the time required is alwaysat mostt.

Logarithmic time

[edit]
Further information:Logarithmic growth

An algorithm is said to takelogarithmic time whenT(n)=O(log⁡n){\displaystyle T(n)=O(\log n)}. Sinceloga⁡n{\displaystyle \log _{a}n} andlogb⁡n{\displaystyle \log _{b}n} are related by aconstant multiplier, and such amultiplier is irrelevant to big O classification, the standard usage for logarithmic-time algorithms isO(log⁡n){\displaystyle O(\log n)} regardless of the base of the logarithm appearing in the expression ofT.

Algorithms taking logarithmic time are commonly found in operations onbinary trees or when usingbinary search.

AnO(log⁡n){\displaystyle O(\log n)} algorithm is considered highly efficient, as the ratio of the number of operations to the size of the input decreases and tends to zero whenn increases. An algorithm that must access all elements of its input cannot take logarithmic time, as the time taken for reading an input of sizen is of the order ofn.

An example of logarithmic time is given by dictionary search. Consider adictionaryD which containsn entries, sorted inalphabetical order. We suppose that, for1≤k≤n{\displaystyle 1\leq k\leq n}, one may access thekth entry of the dictionary in a constant time. LetD(k){\displaystyle D(k)} denote thiskth entry. Under these hypotheses, the test to see if a wordw is in the dictionary may be done in logarithmic time: considerD(⌊n2⌋){\displaystyle D\left(\left\lfloor {\frac {n}{2}}\right\rfloor \right)}, where⌊⌋{\displaystyle \lfloor \;\rfloor } denotes thefloor function. Ifw=D(⌊n2⌋){\displaystyle w=D\left(\left\lfloor {\frac {n}{2}}\right\rfloor \right)}--that is to say, the wordw is exactly in the middle of the dictionary--then we are done. Else, ifw<D(⌊n2⌋){\displaystyle w<D\left(\left\lfloor {\frac {n}{2}}\right\rfloor \right)}--i.e., if the wordw comes earlier in alphabetical order than the middle word of the whole dictionary--we continue the search in the same way in the left (i.e. earlier) half of the dictionary, and then again repeatedly until the correct word is found. Otherwise, if it comes after the middle word, continue similarly with the right half of the dictionary. This algorithm is similar to the method often used to find an entry in a paper dictionary. As a result, the search space within the dictionary decreases as the algorithm gets closer to the target word.

Polylogarithmic time

[edit]

An algorithm is said to run inpolylogarithmic time if its timeT(n){\displaystyle T(n)} isO((log⁡n)k){\displaystyle O{\bigl (}(\log n)^{k}{\bigr )}} for some constantk. Another way to write this isO(logk⁡n){\displaystyle O(\log ^{k}n)}.

For example,matrix chain ordering can be solved in polylogarithmic time on aparallel random-access machine,[7] anda graph can bedetermined to be planar in afully dynamic way inO(log3⁡n){\displaystyle O(\log ^{3}n)} time per insert/delete operation.[8]

Sub-linear time

[edit]

An algorithm is said to run insub-linear time (often spelledsublinear time) ifT(n)=o(n){\displaystyle T(n)=o(n)}. In particular this includes algorithms with the time complexities defined above.

The specific termsublinear time algorithm commonly refers to randomized algorithms that sample a small fraction of their inputs and process them efficiently toapproximately infer properties of the entire instance.[9] This type of sublinear time algorithm is closely related toproperty testing andstatistics.

Other settings where algorithms can run in sublinear time include:

Linear time

[edit]

An algorithm is said to takelinear time, orO(n){\displaystyle O(n)} time, if its time complexity isO(n){\displaystyle O(n)}. Informally, this means that the running time increases at most linearly with the size of the input. More precisely, this means that there is a constantc such that the running time is at mostcn{\displaystyle cn} for every input of sizen. For example, a procedure that adds up all elements of a list requires time proportional to the length of the list, if the adding time is constant, or, at least, bounded by a constant.

Linear time is the best possible time complexity in situations where the algorithm has to sequentially read its entire input. Therefore, much research has been invested into discovering algorithms exhibiting linear time or, at least, nearly linear time. This research includes both software and hardware methods. There are several hardware technologies which exploitparallelism to provide this. An example iscontent-addressable memory. This concept of linear time is used in string matching algorithms such as theBoyer–Moore string-search algorithm andUkkonen's algorithm.

Quasilinear time

[edit]

An algorithm is said to run inquasilinear time (also referred to aslog-linear time) ifT(n)=O(nlogk⁡n){\displaystyle T(n)=O(n\log ^{k}n)} for some positive constantk;[11]linearithmic time is the casek=1{\displaystyle k=1}.[12] Usingsoft O notation these algorithms areO~(n){\displaystyle {\tilde {O}}(n)}. Quasilinear time algorithms are alsoO(n1+ε){\displaystyle O(n^{1+\varepsilon })} for every constantε>0{\displaystyle \varepsilon >0} and thus run faster than any polynomial time algorithm whose time bound includes a termnc{\displaystyle n^{c}} for anyc>1{\displaystyle c>1}.

Algorithms which run in quasilinear time include:

In many cases, theO(nlog⁡n){\displaystyle O(n\log n)} running time is simply the result of performing aΘ(log⁡n){\displaystyle \Theta (\log n)} operationn times (for the notation, seeBig O notation § Family of Bachmann–Landau notations). For example,binary tree sort creates abinary tree by inserting each element of then-sized array one by one. Since the insert operation on aself-balancing binary search tree takesO(log⁡n){\displaystyle O(\log n)} time, the entire algorithm takesO(nlog⁡n){\displaystyle O(n\log n)} time.

Comparison sorts require at leastΩ(nlog⁡n){\displaystyle \Omega (n\log n)} comparisons in the worst case becauselog⁡(n!)=Θ(nlog⁡n){\displaystyle \log(n!)=\Theta (n\log n)}, byStirling's approximation. They also frequently arise from therecurrence relationT(n)=2T(n2)+O(n){\textstyle T(n)=2T\left({\frac {n}{2}}\right)+O(n)}.

Sub-quadratic time

[edit]

Analgorithm is said to besubquadratic time ifT(n)=o(n2){\displaystyle T(n)=o(n^{2})}.

For example, simple, comparison-basedsorting algorithms are quadratic (e.g.insertion sort), but more advanced algorithms can be found that are subquadratic (e.g.shell sort). No general-purpose sorts run in linear time, but the change from quadratic to sub-quadratic is of great practical importance.

Polynomial time

[edit]
Main article:P (complexity)

An algorithm is said to be ofpolynomial time if its running time isupper bounded by apolynomial expression in the size of the input for the algorithm, that is,T(n) =O(nk) for some positive constantk.[1][13]Problems for which a deterministic polynomial-time algorithm exists belong to thecomplexity classP, which is central in the field ofcomputational complexity theory.Cobham's thesis states that polynomial time is a synonym for "tractable", "feasible", "efficient", or "fast".[14]

Some examples of polynomial-time algorithms:

These two concepts are only relevant if the inputs to the algorithms consist of integers.

Complexity classes

[edit]

The concept of polynomial time leads to several complexity classes in computational complexity theory. Some important classes defined using polynomial time are the following.

P is the smallest time-complexity class on a deterministic machine which isrobust in terms of machine model changes. (For example, a change from a single-tape Turing machine to a multi-tape machine can lead to a quadratic speedup, but any algorithm that runs in polynomial time under one model also does so on the other.) Any givenabstract machine will have a complexity class corresponding to the problems which can be solved in polynomial time on that machine.

Superpolynomial time

[edit]

An algorithm is defined to takesuperpolynomial time ifT(n) is not bounded above by any polynomial. Usinglittle omega notation, it isω(nc) time for all constantsc, wheren is the input parameter, typically the number of bits in the input.

For example, an algorithm that runs for 2n steps on an input of sizen requires superpolynomial time (more specifically, exponential time).

An algorithm that uses exponential resources is clearly superpolynomial, but some algorithms are only very weakly superpolynomial. For example, theAdleman–Pomerance–Rumely primality test runs fornO(log logn) time onn-bit inputs; this grows faster than any polynomial for large enoughn, but the input size must become impractically large before it cannot be dominated by a polynomial with small degree.

An algorithm that requires superpolynomial time lies outside thecomplexity classP.Cobham's thesis posits that these algorithms are impractical, and in many cases they are. Since theP versus NP problem is unresolved, it is unknown whetherNP-complete problems require superpolynomial time.

Quasi-polynomial time

[edit]
Main article:Quasi-polynomial time

Quasi-polynomial time algorithms are algorithms whose running time exhibitsquasi-polynomial growth, a type of behavior that may be slower than polynomial time but yet is significantly faster thanexponential time. The worst case running time of a quasi-polynomial time algorithm is2O(logc⁡n){\displaystyle 2^{O(\log ^{c}n)}} for some fixedc>0{\displaystyle c>0}. Whenc=1{\displaystyle c=1} this gives polynomial time, and forc<1{\displaystyle c<1} it gives sub-linear time.

There are some problems for which we know quasi-polynomial time algorithms, but no polynomial time algorithm is known. Such problems arise in approximation algorithms; a famous example is the directedSteiner tree problem, for which there is a quasi-polynomial time approximation algorithm achieving an approximation factor ofO(log3⁡n){\displaystyle O(\log ^{3}n)} (n being the number of vertices), but showing the existence of such a polynomial time algorithm is an open problem.

Other computational problems with quasi-polynomial time solutions but no known polynomial time solution include theplanted clique problem in which the goal is tofind a large clique in the union of a clique and arandom graph. Although quasi-polynomially solvable, it has been conjectured that the planted clique problem has no polynomial time solution; this planted clique conjecture has been used as acomputational hardness assumption to prove the difficulty of several other problems in computationalgame theory,property testing, andmachine learning.[15]

The complexity classQP consists of all problems that have quasi-polynomial time algorithms. It can be defined in terms ofDTIME as follows.[16]

QP=⋃c∈NDTIME(2logc⁡n){\displaystyle {\mbox{QP}}=\bigcup _{c\in \mathbb {N} }{\mbox{DTIME}}\left(2^{\log ^{c}n}\right)}

Relation to NP-complete problems

[edit]

In complexity theory, the unsolvedP versus NP problem asks if all problems in NP have polynomial-time algorithms. All the best-known algorithms forNP-complete problems like 3SAT etc. take exponential time. Indeed, it is conjectured for many natural NP-complete problems that they do not have sub-exponential time algorithms. Here "sub-exponential time" is taken to mean the second definition presented below. (On the other hand, many graph problems represented in the natural way by adjacency matrices are solvable in subexponential time simply because the size of the input is the square of the number of vertices.) This conjecture (for the k-SAT problem) is known as theexponential time hypothesis.[17] Since it is conjectured that NP-complete problems do not have quasi-polynomial time algorithms, some inapproximability results in the field ofapproximation algorithms make the assumption that NP-complete problems do not have quasi-polynomial time algorithms. For example, see the known inapproximability results for theset cover problem.

Sub-exponential time

[edit]

The termsub-exponential time is used to express that the running time of some algorithm may grow faster than any polynomial but is still significantly smaller than an exponential. In this sense, problems that have sub-exponential time algorithms are somewhat more tractable than those that only have exponential algorithms. The precise definition of "sub-exponential" is not generally agreed upon,[18] however the two most widely used are below.

First definition

[edit]

A problem is said to be sub-exponential time solvable if it can be solved in running times whose logarithms grow smaller than any given polynomial. More precisely, a problem is in sub-exponential time if for everyε > 0 there exists an algorithm which solves the problem in timeO(2nε). The set of all such problems is the complexity classSUBEXP which can be defined in terms ofDTIME as follows.[6][19][20][21]

SUBEXP=⋂ε>0DTIME(2nε){\displaystyle {\text{SUBEXP}}=\bigcap _{\varepsilon >0}{\text{DTIME}}\left(2^{n^{\varepsilon }}\right)}

This notion of sub-exponential is non-uniform in terms ofε in the sense thatε is not part of the input and each ε may have its own algorithm for the problem.

Second definition

[edit]

Some authors define sub-exponential time as running times in2o(n){\displaystyle 2^{o(n)}}.[17][22][23] This definition allows larger running times than the first definition of sub-exponential time. An example of such a sub-exponential time algorithm is the best-known classical algorithm for integer factorization, thegeneral number field sieve, which runs in time about2O~(n1/3){\displaystyle 2^{{\tilde {O}}(n^{1/3})}}, where the length of the input isn. Another example was thegraph isomorphism problem, which the best known algorithm from 1982 to 2016 solved in2O(nlog⁡n){\displaystyle 2^{O\left({\sqrt {n\log n}}\right)}}. However, atSTOC 2016 a quasi-polynomial time algorithm was presented.[24]

It makes a difference whether the algorithm is allowed to be sub-exponential in the size of the instance, the number of vertices, or the number of edges. Inparameterized complexity, this difference is made explicit by considering pairs(L,k){\displaystyle (L,k)} ofdecision problems and parametersk.SUBEPT is the class of all parameterized problems that run in time sub-exponential ink and polynomial in the input sizen:[25]

SUBEPT=DTIME(2o(k)⋅poly(n)).{\displaystyle {\text{SUBEPT}}={\text{DTIME}}\left(2^{o(k)}\cdot {\text{poly}}(n)\right).}

More precisely, SUBEPT is the class of all parameterized problems(L,k){\displaystyle (L,k)} for which there is acomputable functionf:N→N{\displaystyle f:\mathbb {N} \to \mathbb {N} } withf∈o(k){\displaystyle f\in o(k)} and an algorithm that decidesL in time2f(k)⋅poly(n){\displaystyle 2^{f(k)}\cdot {\text{poly}}(n)}.

Exponential time hypothesis

[edit]
Main article:Exponential time hypothesis

Theexponential time hypothesis (ETH) is that3SAT, the satisfiability problem of Boolean formulas inconjunctive normal form with at most three literals per clause and withn variables, cannot be solved in time 2o(n). More precisely, the hypothesis is that there is some absolute constantc > 0 such that 3SAT cannot be decided in time 2cn by any deterministic Turing machine. Withm denoting the number of clauses, ETH is equivalent to the hypothesis thatkSAT cannot be solved in time 2o(m) for any integerk ≥ 3.[26] The exponential time hypothesis impliesP ≠ NP.

Exponential time

[edit]

An algorithm is said to beexponential time, ifT(n) is upper bounded by 2poly(n), where poly(n) is some polynomial inn. More formally, an algorithm is exponential time ifT(n) is bounded byO(2nk) for some constantk. Problems which admit exponential time algorithms on a deterministic Turing machine form the complexity class known asEXP.

EXP=⋃c∈R+DTIME(2nc){\displaystyle {\text{EXP}}=\bigcup _{c\in \mathbb {R_{+}} }{\text{DTIME}}\left(2^{n^{c}}\right)}

Sometimes, exponential time is used to refer to algorithms that haveT(n) = 2O(n), where the exponent is at most a linear function ofn. This gives rise to the complexity classE.

E=⋃c∈NDTIME(2cn){\displaystyle {\text{E}}=\bigcup _{c\in \mathbb {N} }{\text{DTIME}}\left(2^{cn}\right)}

Factorial time

[edit]

An algorithm is said to befactorial time ifT(n) is upper bounded by thefactorial functionn!. Factorial time is a subset of exponential time (EXP) becausen!≤nn=2nlog⁡n=O(2n1+ϵ){\displaystyle n!\leq n^{n}=2^{n\log n}=O\left(2^{n^{1+\epsilon }}\right)} for allϵ>0{\displaystyle \epsilon >0}. However, it is not a subset of E.

An example of an algorithm that runs in factorial time isbogosort, a notoriously inefficient sorting algorithm based ontrial and error. Bogosort sorts a list ofn items by repeatedlyshuffling the list until it is found to be sorted. In the average case, each pass through the bogosort algorithm will examine one of then! orderings of then items. If the items are distinct, only one such ordering is sorted. Bogosort shares patrimony with theinfinite monkey theorem.

Double exponential time

[edit]

An algorithm is said to bedouble exponential time ifT(n) is upper bounded by 22poly(n), where poly(n) is some polynomial inn. Such algorithms belong to the complexity class2-EXPTIME.

2-EXPTIME=⋃c∈NDTIME(22nc){\displaystyle {\mbox{2-EXPTIME}}=\bigcup _{c\in \mathbb {N} }{\mbox{DTIME}}\left(2^{2^{n^{c}}}\right)}

Well-known double exponential time algorithms include:

See also

[edit]

References

[edit]
  1. ^abSipser, Michael (2006).Introduction to the Theory of Computation. Course Technology Inc.ISBN 0-619-21764-2.
  2. ^Mehlhorn, Kurt; Naher, Stefan (1990). "Bounded ordered dictionaries inO(log logN) time andO(n) space".Information Processing Letters.35 (4):183–189.doi:10.1016/0020-0190(90)90022-P.
  3. ^Tao, Terence (2010)."1.11 The AKS primality test".An epsilon of room, II: Pages from year three of a mathematical blog. Graduate Studies in Mathematics. Vol. 117. Providence, RI: American Mathematical Society. pp. 82–86.doi:10.1090/gsm/117.ISBN 978-0-8218-5280-4.MR 2780010.
  4. ^Lenstra, H. W. Jr.;Pomerance, Carl (2019)."Primality testing with Gaussian periods"(PDF).Journal of the European Mathematical Society.21 (4):1229–1269.doi:10.4171/JEMS/861.hdl:21.11116/0000-0005-717D-0.MR 3941463.S2CID 127807021.
  5. ^Calude, Cristian S. and Jain, Sanjay and Khoussainov, Bakhadyr and Li, Wei and Stephan, Frank (2017)."Deciding parity games in quasipolynomial time".Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing. Association for Computing Machinery. pp. 252–263.doi:10.1145/3055399.3055409.hdl:2292/31757.ISBN 9781450345286.S2CID 30338402.{{cite book}}: CS1 maint: multiple names: authors list (link)
  6. ^abBabai, László;Fortnow, Lance;Nisan, N.;Wigderson, Avi (1993). "BPP has subexponential time simulations unless EXPTIME has publishable proofs".Computational Complexity.3 (4). Berlin, New York:Springer-Verlag:307–318.doi:10.1007/BF01275486.S2CID 14802332.
  7. ^Bradford, Phillip G.; Rawlins, Gregory J. E.; Shannon, Gregory E. (1998). "Efficient matrix chain ordering in polylog time".SIAM Journal on Computing.27 (2):466–490.doi:10.1137/S0097539794270698.MR 1616556.
  8. ^Holm, Jacob; Rotenberg, Eva (2020). "Fully-dynamic planarity testing in polylogarithmic time". In Makarychev, Konstantin; Makarychev, Yury; Tulsiani, Madhur; Kamath, Gautam;Chuzhoy, Julia (eds.).Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, Chicago, IL, USA, June 22-26, 2020. Association for Computing Machinery. pp. 167–180.arXiv:1911.03449.doi:10.1145/3357713.3384249.ISBN 978-1-4503-6979-4.
  9. ^Kumar, Ravi;Rubinfeld, Ronitt (2003)."Sublinear time algorithms"(PDF).SIGACT News.34 (4):57–67.doi:10.1145/954092.954103.S2CID 65359.
  10. ^Rubinfeld, Ronitt (2019). "Local Computation Algorithms".Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing (PODC). p. 3.doi:10.1145/3293611.3331587.ISBN 978-1-4503-6217-7.
  11. ^Naik, Ashish V.; Regan, Kenneth W.; Sivakumar, D. (1995)."On quasilinear-time complexity theory"(PDF).Theoretical Computer Science.148 (2):325–349.doi:10.1016/0304-3975(95)00031-Q.MR 1355592.
  12. ^Sedgewick, Robert; Wayne, Kevin (2011).Algorithms (4th ed.). Pearson Education. p. 186.
  13. ^Papadimitriou, Christos H. (1994).Computational complexity. Reading, Mass.: Addison-Wesley.ISBN 0-201-53082-1.
  14. ^Cobham, Alan (1965). "The intrinsic computational difficulty of functions".Proc. Logic, Methodology, and Philosophy of Science II. North Holland.
  15. ^Braverman, Mark; Kun-Ko, Young; Rubinstein, Aviad; Weinstein, Omri (2017). "ETH hardness for densest-k-subgraph with perfect completeness". In Klein, Philip N. (ed.).Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16-19. Society for Industrial and Applied Mathematics. pp. 1326–1341.arXiv:1504.08352.doi:10.1137/1.9781611974782.86.ISBN 978-1-61197-478-2.MR 3627815.
  16. ^Complexity Zoo:Class QP: Quasipolynomial-Time
  17. ^abImpagliazzo, Russell; Paturi, Ramamohan (2001)."On the complexity ofk-SAT"(PDF).Journal of Computer and System Sciences.62 (2):367–375.doi:10.1006/jcss.2000.1727.MR 1820597.
  18. ^Aaronson, Scott (5 April 2009)."A not-quite-exponential dilemma".Shtetl-Optimized. Retrieved2 December 2009.
  19. ^Complexity Zoo:Class SUBEXP: Deterministic Subexponential-Time
  20. ^Moser, P. (2003). "Baire's Categories on Small Complexity Classes". In Andrzej Lingas; Bengt J. Nilsson (eds.).Fundamentals of Computation Theory: 14th International Symposium, FCT 2003, Malmö, Sweden, August 12-15, 2003, Proceedings.Lecture Notes in Computer Science. Vol. 2751. Berlin, New York: Springer-Verlag. pp. 333–342.doi:10.1007/978-3-540-45077-1_31.ISBN 978-3-540-40543-6.ISSN 0302-9743.
  21. ^Miltersen, P.B. (2001). "Derandomizing Complexity Classes".Handbook of Randomized Computing. Combinatorial Optimization. Vol. 9. Kluwer Academic Pub. p. 843.doi:10.1007/978-1-4615-0013-1_19 (inactive 1 November 2024).ISBN 978-1-4613-4886-3.{{cite book}}: CS1 maint: DOI inactive as of November 2024 (link)
  22. ^Kuperberg, Greg (2005). "A Subexponential-Time Quantum Algorithm for the Dihedral Hidden Subgroup Problem".SIAM Journal on Computing.35 (1). Philadelphia: 188.arXiv:quant-ph/0302112.doi:10.1137/s0097539703436345.ISSN 1095-7111.S2CID 15965140.
  23. ^Oded Regev (2004). "A Subexponential Time Algorithm for the Dihedral Hidden Subgroup Problem with Polynomial Space".arXiv:quant-ph/0406151v1.
  24. ^Grohe, Martin; Neuen, Daniel (2021). "Recent advances on the graph isomorphism problem". In Dabrowski, Konrad K.; Gadouleau, Maximilien; Georgiou, Nicholas; Johnson, Matthew; Mertzios, George B.; Paulusma, Daniël (eds.).Surveys in combinatorics 2021. London Mathematical Society Lecture Note Series. Vol. 470. Cambridge University Press. pp. 187–234.arXiv:2011.01366.ISBN 978-1-009-01888-3.MR 4273431.
  25. ^Flum, Jörg;Grohe, Martin (2006).Parameterized Complexity Theory. Springer. p. 417.ISBN 978-3-540-29952-3.
  26. ^Impagliazzo, R.; Paturi, R.; Zane, F. (2001)."Which problems have strongly exponential complexity?".Journal of Computer and System Sciences.63 (4):512–530.doi:10.1006/jcss.2001.1774.
  27. ^Mayr, Ernst W.;Meyer, Albert R. (1982)."The complexity of the word problems for commutative semigroups and polynomial ideals".Advances in Mathematics.46 (3):305–329.doi:10.1016/0001-8708(82)90048-2.hdl:1721.1/149010.MR 0683204.
  28. ^Davenport, James H.;Heintz, Joos (1988)."Real quantifier elimination is doubly exponential".Journal of Symbolic Computation.5 (1–2):29–35.doi:10.1016/S0747-7171(88)80004-X.MR 0949111.
  29. ^Collins, George E. (1975). "Quantifier elimination for real closed fields by cylindrical algebraic decomposition". In Brakhage, H. (ed.).Automata Theory and Formal Languages: 2nd GI Conference, Kaiserslautern, May 20–23, 1975. Lecture Notes in Computer Science. Vol. 33. Springer. pp. 134–183.doi:10.1007/3-540-07407-4_17.ISBN 978-3-540-07407-6.MR 0403962.

Retrieved from "https://en.wikipedia.org/w/index.php?title=Time_complexity&oldid=1283310941#Constant_time"
Categories:
Hidden categories:
[8]ページ先頭
©2009-2025 Movatter.jp