| dbo:abstract
|
- في علم الحاسوب، يعتبر تعقيد الوقت هو التعقيد الحسابي الذي يقيس أو يقدر الوقت المستغرق لتشغيل خوارزمية. عادةً ما يتم تقدير تعقيد الوقت من خلال حساب عدد العمليات الأولية التي تقوم بها الخوارزمية، بافتراض أن العملية الأولية تستغرق وقتًا ثابتًا لأداءها. وبالتالي، فإن مقدار الوقت المستغرق وعدد العمليات الأولية التي تقوم بها الخوارزمية يختلفان على الأكثر بعامل ثابت. نظرًا لأن وقت تشغيل الخوارزمية قد يختلف باختلاف مدخلات من نفس الحجم، فيحسب المرء عادة تعقيد وقت الحالة الأسوأ، وهو أقصى مقدار من الوقت المستغرق في مدخلات حجم معين. أقل شيوعا، وعادة ما يتم تحديده بشكل صريح، هو تعقيد الحالة المتوسطة، وهو متوسط الوقت المستغرق على مدخلات حجم معين (وهذا منطقي، حيث لا يوجد سوى عدد محدود من المدخلات الممكنة من حجم معين). في كلتا الحالتين، يتم التعبير عن تعقيد الوقت بشكل عام كدالة لحجم المدخلات. بما أن هذه الوظيفة يصعب بشكل عام حسابها بالضبط، ووقت التشغيل عادة لا يكون حرجًا بالنسبة إلى المدخلات الصغيرة، فإن أحدهما يركز عادة على سلوك التعقيد عندما يزيد حجم المدخلات؛ وهذا هو، على السلوك المقارب للتعقيد. لذلك، يتم التعبير عن تعقيد الوقت بشكل شائع باستخدام تدوين O الكبير، عادةً، إلخ، حيث n هو حجم الإدخال المقاس بعدد البتات المطلوبة لتمثيله. بت يتم تصنيف تعقيدات الخوارزمية بواسطة الدالة التي تظهر في تدوين O الكبير. على سبيل المثال، خوارزمية ذات تعقيد زمني هي خوارزمية زمنية خطية ، خوارزمية مع تعقيد زمني لبعض الثابت هي خوارزمية زمن متعددة الحدود .'' (ar)
- Při řešení úloh pomocí výpočetní techniky musíme mít nástroj, kterým dokážeme porovnat efektivitu a rychlost vykonávání jednotlivých algoritmů. Pro tento účel byly zavedeny pojmy asymptotická složitost a operační náročnost algoritmu. Asymptotická složitost je způsob klasifikace počítačových algoritmů. Určuje operační náročnost algoritmu tak, že zjišťuje, jakým způsobem se bude chování algoritmu měnit v závislosti na změně velikosti (počtu) vstupních dat. Zapisuje se pomocí Landauovy notace (též „Omikron notace“, nebo „velké O notace“) jako (např. ). Obvykle se používá asymptotická časová a prostorová složitost. Používaný zápis znamená, že náročnost algoritmu je menší než , kde a jsou vhodně zvolené konstanty a je veličina popisující velikost vstupních dat. Zanedbáváme tedy multiplikativní i aditivní konstanty, tzn. . Zajímá nás jen chování funkce pro velké hodnoty . Například časová složitost (tzv. lineární) říká, že doba trvání práce algoritmu se zvýší přibližně tolikrát, kolikrát se zvýší velikost vstupu. Na druhou stranu u složitosti se doba trvání průběhu zvyšuje kvadraticky, tedy pokud se zvýší délka vstupu dvakrát, potřebný čas se zvýší přibližně čtyřikrát. U časové složitosti naopak na délce vstupu vůbec nezáleží a potřebný čas nepřevýší nějakou pevnou mez. Podobně je tomu i u prostorové složitosti, jen s tou změnou, že se jedná o potřebné paměťové (prostorové) nároky v závislosti na délce vstupních dat. (cs)
- En informática, la complejidad temporal es la complejidad computacional que describe la cantidad de tiempo que lleva ejecutar un algoritmo. La complejidad temporal se estima comúnmente contando el número de operaciones elementales realizadas por el algoritmo, suponiendo que cada operación elemental requiere una cantidad fija de tiempo. Por lo tanto, la cantidad de tiempo necesario y el número de operaciones elementales realizadas por el algoritmo difieren en un factor constante como máximo. Dado que el tiempo de ejecución de un algoritmo puede variar entre diferentes entradas del mismo tamaño, comúnmente se considera la complejidad temporal del peor caso, que es la cantidad máxima de tiempo requerida para las entradas de un tamaño determinado. Menos común, y usualmente especificado explícitamente, es la complejidad del caso promedio, que es el promedio del tiempo necesario para las entradas de un tamaño dado (esto tiene sentido porque solo hay un número finito de entradas posibles de un tamaño dado). En ambos casos, la complejidad temporal generalmente se expresa como una función del tamaño de la entrada. Dado que esta función es generalmente difícil de calcular exactamente, y el tiempo de ejecución para entradas pequeñas generalmente no es consecuente, uno comúnmente se enfoca en el comportamiento de la complejidad cuando aumenta el tamaño de entrada, es decir, el comportamiento asintótico de la complejidad. Por lo tanto, la complejidad temporal se expresa comúnmente usando la notación O grande, típicamente etc., donde n es el tamaño de entrada en unidades de bits necesarios para representar la entrada. Las complejidades algorítmicas se clasifican según el tipo de función que aparece en la notación O grande. Por ejemplo, un algoritmo con complejidad temporal es un algoritmo de tiempo lineal y un algoritmo con complejidad de tiempo por alguna constante es un algoritmo de tiempo polinómico . (es)
- Unter der Zeitkomplexität eines Problems wird in der Informatik die Anzahl der Rechenschritte verstanden, die ein optimaler Algorithmus zur Lösung dieses Problems benötigt, in Abhängigkeit von der Länge der Eingabe. Man spricht hier auch von der asymptotischen Laufzeit und meint damit, in Anlehnung an eine Asymptote, das Zeitverhalten des Algorithmus für eine potenziell unendlich große Eingabemenge. Es interessiert also nicht der Zeitaufwand eines konkreten Programms auf einem bestimmten Computer, sondern viel mehr, wie der Zeitbedarf wächst, wenn mehr Daten zu verarbeiten sind, also z. B. ob sich der Aufwand für die doppelte Datenmenge verdoppelt oder quadriert (Skalierbarkeit). Die Laufzeit wird daher in Abhängigkeit von der Länge n der Eingabe angegeben und für immer größer werdende n asymptotisch unter Verwendung der Landau-Notation (Groß-O-Notation) abgeschätzt. Eine genauere Laufzeitabschätzung von Rekursionsgleichungen bietet auch das Mastertheorem oder die Substitutionsmethode. Wird der Begriff der Zeitkomplexität auf einen konkreten Algorithmus bezogen, so ist damit die Anzahl der Schritte gemeint, die der Algorithmus für die Bearbeitung einer Eingabe mit bestimmter Länge n benötigt (im besten, schlechtesten oder durchschnittlichen Fall, siehe unten). In der Komplexitätstheorie ist der eigentliche Gegenstand der Betrachtung aber die Komplexität von Problemen. Die Komplexität von Algorithmen ist nur insofern interessant, als daraus Aussagen über das behandelte Problem geschlossen werden können. In der Praxis ist diese aber häufig interessant, vor allem um für einen konkreten Kontext einen geeigneten Algorithmus auszuwählen: So ist Bubblesort zwar für große Datenmengen ein recht langsames Verfahren, eignet sich aber aufgrund des geringen Overheads gut für kleine Datenmengen (insbesondere für n ≤ 8). Die Zeitkomplexität wird immer in Bezug auf ein Maschinenmodell angegeben. In der Regel ist das Bezugsmodell die Turingmaschine, alternativ kann die Zeitkomplexität aber auch in Bezug auf eine Registermaschine angegeben werden, die in ihrem Verhalten mehr den tatsächlich existierenden Computern ähnelt. Für parallele Algorithmen kann ein paralleles Maschinenmodell wie die PRAM verwendet werden. Ein in Beziehung zum PRAM Modell stehendes Modell ist das Externspeichermodell. Jedes Problem, welches effizient im PRAM gelöst werden kann, kann auch effizient im Externspeicher berechnet werden. Zudem wird zwischen der Komplexität für deterministische und nichtdeterministische Maschinen unterschieden. In der Komplexitätstheorie ist die Zeitkomplexität neben der Platzkomplexität der am häufigsten untersuchte Aspekt von Algorithmen und Problemen. Die Zeitkomplexität aller Algorithmen, die ein Problem lösen, liegt beispielsweise einer Reihe bedeutsamer Komplexitätsklassen zu Grunde. (de)
- En algorithmique, la complexité en temps est une mesure du temps utilisé par un algorithme, exprimé comme fonction de la taille de l'entrée. Le temps compte le nombre d'étapes de calcul avant d'arriver à un résultat. Usuellement le temps correspondant à des entrées de taille n est le temps le plus long parmi les temps d’exécution des entrées de cette taille ; on parle de complexité dans le pire cas. Les études de complexité portent dans la majorité des cas sur le comportement asymptotique, lorsque la taille des entrées tend vers l'infini, et l'on utilise couramment les notations grand O de Landau. La complexité en temps étant la mesure la plus courante en algorithmique, on parle parfois simplement de la complexité d'un algorithme, mais il existe d'autres mesures comme la complexité en espace. Calculer les complexités d'un algorithme, et en particulier la complexité en temps est parfois complexe, et cette étude constitue en elle-même une discipline : l'analyse de la complexité des algorithmes. (fr)
- In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. 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 a constant factor. Since an algorithm's running time may vary among different inputs of the same size, one commonly considers the worst-case time complexity, which is the maximum amount of time required for inputs of a given size. Less common, and usually specified explicitly, is the average-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 a function of the size of the input. 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, the asymptotic behavior of the complexity. Therefore, the time complexity is commonly expressed using big O notation, typically , , , , etc., where n is the size in units of bits 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 complexity is a linear time algorithm and an algorithm with time complexity for some constant is a polynomial time algorithm. (en)
- ( 러닝 타임은 여기로 연결됩니다. 매체의 재생·상영 시간에 대해서는 러닝 타임 (매체) 문서를 참고하십시오.) 계산 복잡도 이론에서 시간 복잡도는 문제를 해결하는데 걸리는 시간과 입력의 함수 관계를 가리킨다. 컴퓨터과학에서 알고리즘의 시간복잡도는 입력을 나타내는 문자열 길이의 함수로서 작동하는 알고리즘을 취해 시간을 정량화하는 것이다. 알고리즘의 시간복잡도는 주로 빅-오 표기법을 사용하여 나타내며, 이 빅-오 표기법은 계수와 낮은 차수의 항을 제외시키는 방법이다. 이런 방식으로 표현할 때, (예를 들면, 입력 크기를 무한대로 입력하여) 시간복잡도를 점근적으로 묘사한다고 말한다. 예시로서, 만약 크기 n의 모든 입력에 대한 알고리즘에 필요한 시간이 최대 (어떤 n0보다 크지 않은 모든 n에 대하여) 5n3 + 3n의 식을 가진다면, 이 알고리즘의 점근적 시간 복잡도는 O(n3)이라고 할 수 있다. 시간 복잡도는 기본적인 연산을 수행하는데에 어떤 고정된 시간이 걸릴 때, 알고리즘에 의해서 수행되는 기본 연산의 개수를 세어 예측할 수 있다. 그러므로 걸리는 시간의 총량과 알고리즘에 의해 수행되는 기본적인 연산의 개수는 최대 상수 인자만큼 다르다. 알고리즘의 수행 시간은 동일 크기의 다양한 입력에 의해 달라질 수 있기 때문에, 가장 많이 쓰이는 최악의 시간 복잡도의 알고리즘 시간을 T(n)이라고 했을 때, 이것은 크기 n의 모든 입력에 대해 걸리는 최대의 시간으로 정의할 수 있다. 그 다음으로 덜 흔하게 쓰이면서, 보통 명확하게 서술되는 측정방법은 평균 시간 복잡도이다. 시간 복잡도는 함수 T(n)의 특성에 의해 분류할 수 있다. 예를 들면, T(n)=O(n)인 알고리즘은 선형 시간 알고리즘이라고 부르며, 몇몇 M ≥ n >1에 대해 T(n)=O(Mn)이고 Mn=O(T(n)) 인 알고리즘은 지수 시간 알고리즘이라고 한다. (ko)
- In informatica, la complessità temporale di un algoritmo quantifica la quantità di tempo impiegata da un algoritmo a essere eseguito in funzione della lunghezza della stringa che rappresenta l'input:226. La complessità temporale di un algoritmo è espressa comunemente usando la notazione O-grande, che esclude i coefficienti e i termini di ordine inferiore. Quando è espressa in questo modo, si dice che la complessità temporale è descritta asintoticamente, ossia, quando la dimensione degli input va a infinito. Ad esempio, se il tempo richiesto da un algoritmo su tutti gli input di dimensione n è al massimo 5n3 + 3n, la complessità temporale asintotica è O(n3). La complessità temporale è stimata comunemente contando il numero di operazioni elementari eseguite dall'algoritmo, dove un'operazione elementare impiega una quantità di tempo fissa a essere eseguita. Così la quantità di tempo impiegata e il numero di operazioni elementari eseguite dall'algoritmo differiscono al massimo di un fattore costante. Poiché il tempo di esecuzione di un algoritmo può variare con diversi input della stessa dimensione, si usa comunemente la complessità temporale del caso peggiore di un algoritmo, denotata come T(n), che è definita come la quantità di tempo massimo impiegata su qualsiasi input di dimensione n. Le complessità temporali sono classificate in base alla natura della funzione T(n). Ad esempio, un algoritmo con T(n) = O(n) è chiamato algoritmo in tempo lineare, e un algoritmo con T(n) = O(2n) si dice che è un algoritmo in tempo esponenziale. (it)
- Inom datavetenskapen är tidskomplexitet beräkningskomplexiteten för en algoritm mätt i tid. Tidskomplexitet beräknas genom att man estimerar tidskostnaden för de elementära operationer som krävs i en algoritm. Vanligtvis beror antalet steg på hur stort problemstorleken är, det vill säga indatastorlek, varför man uttrycker tidskomplexitet som en funktion av problemstorleken. Ofta är olika typer av probleminstanser svårare eller lättare för en algoritm. Om så är fallet kan man gör en bästa fallet-analys, en värsta fallet-analys eller en genomsnittsanalys. (sv)
- Часова складність алгоритму в комп'ютерних науках є обчислювальною складністю алгоритму, яка описує час потрібний для виконання алгоритму. Вона зазвичай визначається шляхом підрахунку кількості елементарних операцій, виконуваних алгоритмом, при цьому вважають, що кожна елементарна операція виконується за фіксовану кількість часу. Таким чином, кількість часу і кількість елементарних операцій, необхідних для виконання алгоритму, відрізняються постійним множником. Оскільки час роботи алгоритму може відрізнятися на вхідних даних одного розміру, то зазвичай розглядається найгірший випадок складності, який відповідає максимальному часу, необхідного для виконання при вхідних даних заданого розміру. Менш поширеною і, як правило, явно вказаною є , яка є середньою величиною часу на вхідні дані даного розміру (це має сенс, оскільки існує лише скінченне число можливих вхідних даних даного розміру). В обох випадках часова складність алгоритму є функцією від розміру вхідних даних. Оскільки ці функції, як правило, важко точно розрахувати, а час роботи у випадку невеликого розміру вхідних даних, не завжди прогнозований, тому зазвичай оцінюють поведінку складності при збільшенні розміру вхідних даних, тобто асимптотичну поведінку складності алгоритму. Це пояснює, чому зазвичай часову складність часто описують за допомогою нотації великого О, зазвичай і т. д., де n відповідає розміру вхідних даних в одиницях вимірювання або в бітах, які потрібні для їх представлення. Алгоритмічна складність класифікується відповідно до типу функції, яка її описує в нотації великого О. Наприклад, алгоритм зі складністю є алгоритмом лінійної складності, а алгоритм зі складністю для деякої константи є алгоритмом поліноміальної складності. (uk)
- 在计算机科学中，算法的时间复杂度（Time complexity）是一个函数，它定性描述该算法的运行时间。这是一个代表算法输入值的字符串的长度的函数。时间复杂度常用大O符号表述，不包括这个函数的低阶项和首项系数。使用这种方式时，时间复杂度可被称为是渐近的，亦即考察输入值大小趋近无穷时的情况。例如，如果一个算法对于任何大小为 n （必須比 n0 大）的输入，它至多需要 5n3 + 3n 的时间运行完毕，那么它的渐近时间复杂度是 O(n3)。 為了計算時間複雜度，我們通常會估計算法的操作單元數量，每個單元執行的時間都是相同的。因此，總運行時間和算法的操作單元數量最多相差一个常量系数。 相同大小的不同輸入值仍可能造成算法的執行時間不同，因此我們通常使用算法的，記為 T(n) ，定義為任何大小的輸入 n 所需的最大執行時間。另一種較少使用的方法是，通常有特別指定才會使用。時間複雜度可以用函數 T(n) 的自然特性加以分類，舉例來說，有著 T(n) = O(n) 的算法被稱作「線性時間算法」；而 T(n) = O(Mn) 和 Mn= O(T(n)) ，其中 M ≥ n > 1 的算法被稱作「指數時間算法」。 (zh)
- В информатике временна́я сложность алгоритма определяется как функция от длины строки, представляющей входные данные, равная времени работы алгоритма на данном входе. Временная сложность алгоритма обычно выражается с использованием нотации «O» большое, которая учитывает только слагаемое самого высокого порядка, а также не учитывает константные множители, то есть коэффициенты. Если сложность выражена таким способом, говорят об асимптотическом описании временной сложности, то есть при стремлении размера входа к бесконечности. Например, если существует число , такое, что время работы алгоритма для всех входов длины не превосходит , то временную сложность данного алгоритма можно асимптотически оценить как . Временная сложность обычно оценивается путём подсчёта числа элементарных операций, осуществляемых алгоритмом. Время исполнения одной такой операции при этом берётся константой, то есть асимптотически оценивается как . В таких обозначениях полное время исполнения и число элементарных операций, выполненных алгоритмом, отличаются максимум на постоянный множитель, который не учитывается в O-нотации. Так как время работы алгоритма может отличаться на входах одного и того же размера, обычно используется , которое обозначается как и определяется как наибольшее по всем входным данным длины время работы алгоритма. Реже, и это обычно оговаривается специально, вычисляется , то есть математическое ожидание времени работы по всем возможным входам. Время работы алгоритма может быть классифицировано в зависимости от того, какая функция находится под О-нотацией. Например, алгоритм с называют алгоритмом с линейным временем работы, а алгоритм с для некоторого называют полиномиальным. (ru)
|
| rdfs:comment
|
- Inom datavetenskapen är tidskomplexitet beräkningskomplexiteten för en algoritm mätt i tid. Tidskomplexitet beräknas genom att man estimerar tidskostnaden för de elementära operationer som krävs i en algoritm. Vanligtvis beror antalet steg på hur stort problemstorleken är, det vill säga indatastorlek, varför man uttrycker tidskomplexitet som en funktion av problemstorleken. Ofta är olika typer av probleminstanser svårare eller lättare för en algoritm. Om så är fallet kan man gör en bästa fallet-analys, en värsta fallet-analys eller en genomsnittsanalys. (sv)
- 在计算机科学中，算法的时间复杂度（Time complexity）是一个函数，它定性描述该算法的运行时间。这是一个代表算法输入值的字符串的长度的函数。时间复杂度常用大O符号表述，不包括这个函数的低阶项和首项系数。使用这种方式时，时间复杂度可被称为是渐近的，亦即考察输入值大小趋近无穷时的情况。例如，如果一个算法对于任何大小为 n （必須比 n0 大）的输入，它至多需要 5n3 + 3n 的时间运行完毕，那么它的渐近时间复杂度是 O(n3)。 為了計算時間複雜度，我們通常會估計算法的操作單元數量，每個單元執行的時間都是相同的。因此，總運行時間和算法的操作單元數量最多相差一个常量系数。 相同大小的不同輸入值仍可能造成算法的執行時間不同，因此我們通常使用算法的，記為 T(n) ，定義為任何大小的輸入 n 所需的最大執行時間。另一種較少使用的方法是，通常有特別指定才會使用。時間複雜度可以用函數 T(n) 的自然特性加以分類，舉例來說，有著 T(n) = O(n) 的算法被稱作「線性時間算法」；而 T(n) = O(Mn) 和 Mn= O(T(n)) ，其中 M ≥ n > 1 的算法被稱作「指數時間算法」。 (zh)
- في علم الحاسوب، يعتبر تعقيد الوقت هو التعقيد الحسابي الذي يقيس أو يقدر الوقت المستغرق لتشغيل خوارزمية. عادةً ما يتم تقدير تعقيد الوقت من خلال حساب عدد العمليات الأولية التي تقوم بها الخوارزمية، بافتراض أن العملية الأولية تستغرق وقتًا ثابتًا لأداءها. وبالتالي، فإن مقدار الوقت المستغرق وعدد العمليات الأولية التي تقوم بها الخوارزمية يختلفان على الأكثر بعامل ثابت. في كلتا الحالتين، يتم التعبير عن تعقيد الوقت بشكل عام كدالة لحجم المدخلات. بت (ar)
- Při řešení úloh pomocí výpočetní techniky musíme mít nástroj, kterým dokážeme porovnat efektivitu a rychlost vykonávání jednotlivých algoritmů. Pro tento účel byly zavedeny pojmy asymptotická složitost a operační náročnost algoritmu. Používaný zápis znamená, že náročnost algoritmu je menší než , kde a jsou vhodně zvolené konstanty a je veličina popisující velikost vstupních dat. Zanedbáváme tedy multiplikativní i aditivní konstanty, tzn. . Zajímá nás jen chování funkce pro velké hodnoty . (cs)
- Unter der Zeitkomplexität eines Problems wird in der Informatik die Anzahl der Rechenschritte verstanden, die ein optimaler Algorithmus zur Lösung dieses Problems benötigt, in Abhängigkeit von der Länge der Eingabe. Man spricht hier auch von der asymptotischen Laufzeit und meint damit, in Anlehnung an eine Asymptote, das Zeitverhalten des Algorithmus für eine potenziell unendlich große Eingabemenge. Es interessiert also nicht der Zeitaufwand eines konkreten Programms auf einem bestimmten Computer, sondern viel mehr, wie der Zeitbedarf wächst, wenn mehr Daten zu verarbeiten sind, also z. B. ob sich der Aufwand für die doppelte Datenmenge verdoppelt oder quadriert (Skalierbarkeit). Die Laufzeit wird daher in Abhängigkeit von der Länge n der Eingabe angegeben und für immer größer werdende n a (de)
- En informática, la complejidad temporal es la complejidad computacional que describe la cantidad de tiempo que lleva ejecutar un algoritmo. La complejidad temporal se estima comúnmente contando el número de operaciones elementales realizadas por el algoritmo, suponiendo que cada operación elemental requiere una cantidad fija de tiempo. Por lo tanto, la cantidad de tiempo necesario y el número de operaciones elementales realizadas por el algoritmo difieren en un factor constante como máximo. (es)
- En algorithmique, la complexité en temps est une mesure du temps utilisé par un algorithme, exprimé comme fonction de la taille de l'entrée. Le temps compte le nombre d'étapes de calcul avant d'arriver à un résultat. La complexité en temps étant la mesure la plus courante en algorithmique, on parle parfois simplement de la complexité d'un algorithme, mais il existe d'autres mesures comme la complexité en espace. (fr)
- In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. 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 a constant factor. (en)
- In informatica, la complessità temporale di un algoritmo quantifica la quantità di tempo impiegata da un algoritmo a essere eseguito in funzione della lunghezza della stringa che rappresenta l'input:226. La complessità temporale di un algoritmo è espressa comunemente usando la notazione O-grande, che esclude i coefficienti e i termini di ordine inferiore. Quando è espressa in questo modo, si dice che la complessità temporale è descritta asintoticamente, ossia, quando la dimensione degli input va a infinito. Ad esempio, se il tempo richiesto da un algoritmo su tutti gli input di dimensione n è al massimo 5n3 + 3n, la complessità temporale asintotica è O(n3). (it)
- ( 러닝 타임은 여기로 연결됩니다. 매체의 재생·상영 시간에 대해서는 러닝 타임 (매체) 문서를 참고하십시오.) 계산 복잡도 이론에서 시간 복잡도는 문제를 해결하는데 걸리는 시간과 입력의 함수 관계를 가리킨다. 컴퓨터과학에서 알고리즘의 시간복잡도는 입력을 나타내는 문자열 길이의 함수로서 작동하는 알고리즘을 취해 시간을 정량화하는 것이다. 알고리즘의 시간복잡도는 주로 빅-오 표기법을 사용하여 나타내며, 이 빅-오 표기법은 계수와 낮은 차수의 항을 제외시키는 방법이다. 이런 방식으로 표현할 때, (예를 들면, 입력 크기를 무한대로 입력하여) 시간복잡도를 점근적으로 묘사한다고 말한다. 예시로서, 만약 크기 n의 모든 입력에 대한 알고리즘에 필요한 시간이 최대 (어떤 n0보다 크지 않은 모든 n에 대하여) 5n3 + 3n의 식을 가진다면, 이 알고리즘의 점근적 시간 복잡도는 O(n3)이라고 할 수 있다. 시간 복잡도는 기본적인 연산을 수행하는데에 어떤 고정된 시간이 걸릴 때, 알고리즘에 의해서 수행되는 기본 연산의 개수를 세어 예측할 수 있다. 그러므로 걸리는 시간의 총량과 알고리즘에 의해 수행되는 기본적인 연산의 개수는 최대 상수 인자만큼 다르다. (ko)
- Часова складність алгоритму в комп'ютерних науках є обчислювальною складністю алгоритму, яка описує час потрібний для виконання алгоритму. Вона зазвичай визначається шляхом підрахунку кількості елементарних операцій, виконуваних алгоритмом, при цьому вважають, що кожна елементарна операція виконується за фіксовану кількість часу. Таким чином, кількість часу і кількість елементарних операцій, необхідних для виконання алгоритму, відрізняються постійним множником. (uk)
- В информатике временна́я сложность алгоритма определяется как функция от длины строки, представляющей входные данные, равная времени работы алгоритма на данном входе. Временная сложность алгоритма обычно выражается с использованием нотации «O» большое, которая учитывает только слагаемое самого высокого порядка, а также не учитывает константные множители, то есть коэффициенты. Если сложность выражена таким способом, говорят об асимптотическом описании временной сложности, то есть при стремлении размера входа к бесконечности. Например, если существует число , такое, что время работы алгоритма для всех входов длины не превосходит , то временную сложность данного алгоритма можно асимптотически оценить как . (ru)
|
