翻訳と辞書
Words near each other
・ Time hierarchy theorem
・ Time High Fiction
・ Time Hollow
・ Time Honoured Ghosts
・ Time horizon
・ Time Hunter
・ Time I
・ Time charter equivalent
・ Time Chasers
・ Time Circle, 1968–1972
・ Time clock
・ Time code ambiguity
・ Time Commander
・ Time Commanders
・ Time Commando
Time complexity
・ Time Considered as a Helix of Semi-Precious Stones
・ Time Considered as a Helix of Semi-Precious Stones – The BBC Sessions 1979–1984
・ Time consistency
・ Time constant
・ Time constraint
・ Time Control
・ Time control
・ Time Cracks
・ Time Crash
・ Time Crash (band)
・ Time Crashers
・ Time Crisis
・ Time Crisis (series)
・ Time Crisis 3


Dictionary Lists
翻訳と辞書 辞書検索 [ 開発暫定版 ]
スポンサード リンク

Time complexity : ウィキペディア英語版
Time complexity

In computer science, the time complexity of an algorithm quantifies the amount of time taken by an algorithm to run as a function of the length of the string representing the input〔. The time complexity of an algorithm is commonly expressed using big O notation, which excludes coefficients and lower order terms. When expressed this way, the time complexity is said to be described ''asymptotically'', i.e., as the input size goes to infinity. For example, if the time required by an algorithm on all inputs of size ''n'' is at most for any ''n'' (bigger than some ''n0''), the asymptotic time complexity is O(''n''3).
Time complexity is commonly estimated by counting the number of elementary operations performed by the algorithm, where an 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 differ by at most a constant factor.
Since an algorithm's performance time may vary with different inputs of the same size, one commonly uses the worst-case time complexity of an algorithm, denoted as ''T''(''n''), which is defined as the maximum amount of time taken on any input of size ''n''. Less common, and usually specified explicitly, is the measure of average-case complexity. Time complexities are classified by the nature of the function ''T''(''n''). For instance, an algorithm with ''T''(''n'') = ''O''(''n'') is called a ''linear time algorithm'', and an algorithm with ''T''(''n'') = ''O''(''M''''n'') and ''m''''n''= O(''T''(''n'')) for some ''M'' ≥ ''n'' > 1 is said to be an ''exponential time algorithm''.
==Table of common time complexities==

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

抄文引用元・出典: フリー百科事典『 ウィキペディア(Wikipedia)
ウィキペディアで「Time complexity」の詳細全文を読む



スポンサード リンク
翻訳と辞書 : 翻訳のためのインターネットリソース

Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.