In computer science, the analysis of algorithms is the process of finding the computational complexity of algorithms – the amount of time, storage, or other resources needed to execute them. Usually, this involves determining a function that relates the length of an algorithm's input to the number of steps it takes (its time complexity) or the number of storage locations it uses (its space complexity). An algorithm is said to be efficient when this function's values are small, or grow slowly compared to a growth in the size of the input. Different inputs of the same length may cause the algorithm to have different behavior, so best, worst and average case descriptions might all be of practical interest. When not otherwise specified, the function describing the performance of an algorithm i

Property Value
dbo:abstract
  • تحليل الخوارزميات هو تحديد مقدار الموارد (Resources) (مثل الوقت وسعة التخزين) اللازمة لتنفيذ هذه الخوارزمية. معظم الخوارزميات تصمم للعمل مع مدخلات مطلقة الطول. عادة كفاءة والتعقيد لخوارزمية يتحدد كدالة تتبع إلى عدد الخطوات (تعقيد الوقت time complexity) أو أماكن التخزين (تعقيد المكان space complexity) تحليل الخوارزميات جزء مهم من نظرية التعقيد الحسابي لأنها تؤمن تقدير نظري للموارد اللازمة من أجل إنجاز خوارزمية لحل مسألة تحسبيبة. (ar)
  • L'anàlisi d'algorismes és una part important de la teoria de complexitat computacional més àmplia, que proveeix estimacions teòriques per als recursos que necessita qualsevol algorisme que resolgui un problema computacional donat. Aquestes estimacions resulten ser bastant útils en la recerca d'algorismes eficients. A l'hora de realitzar una anàlisi teòrica d'algorismes és comú calcular la seva complexitat en un sentit asimptòtic, és a dir, per una mida d'entrada suficientment gran. La , i les notacions i s'usen amb aquesta finalitat. Per exemple, la cerca binària diem que s'executa en una quantitat de passos proporcional a un logaritme, en O (log (n)), col·loquialment "en temps logarítmic". Normalment les estimacions asimptòtiques s'utilitzen perquè diferents implementacions del mateix algorisme no tenen per què tenir la mateixa eficiència. No obstant l'eficiència de dues implementacions "raonables" qualssevol d'un algorisme donat estan relacionades per una constant multiplicativa trucada constant oculta. La mesura exacta (no asimptòtica) de l'eficiència de vegades pot ser computada però per a això sol fer falta acceptar supòsits sobre la implementació concreta de l'algorisme, anomenada . Un model de computació pot definir en termes d'un ordinador abstracte, com la Màquina de Turing, i/o postulant que certes operacions s'executen en una unitat de temps.Per exemple, si al conjunt ordenat al que apliquem una cerca binària té n elements, i podem garantir que una única cerca binària pot realitzar en un temps unitari, llavors es requereixen com molt log 2 N+1 unitats de temps per tornar una resposta. Les mesures exactes d'eficiència són útils per als qui veritablement implementen i fan servir algoritmes, perquè tenen més precisió i així els permet saber quant temps poden suposar que prendrà l'execució. Per a algunes persones, com els desenvolupadors de videojocs, una constant oculta pot significar la diferència entre èxit i fracàs. Les estimacions de temps depenen de com definim un pas. Perquè l'anàlisi tingui sentit, hem de garantir que el temps requerit per realitzar un pas estigui acotat superiorment per una constant. Cal mantenir previngut en aquest terreny, per exemple, algunes anàlisis compten que la suma de dos nombres es fa en un pas. Aquest supòsit pot no estar garantit en certs contextos. Si per exemple els nombres involucrats en la computació poden ser arbitràriament grans, deixem de poder assumir que l'addició requereix un temps constant (usant paper i llapis, compara el temps que necessites per sumar dos enters de 2 dígits cadascun i el necessari per fer-ho amb enters de 1000 dígits). (ca)
  • Analýza algoritmů je v matematické informatice určení rozsahu výpočetních prostředků potřebných k vykonání algoritmu. Jako primární kritéria náročnosti algoritmu se volí doba běhu a použitý paměťový prostor. Většina algoritmů je navržena tak, že mohou přijímat vstup o libovolné délce. Nákladnost (složitost) algoritmu je obvykle vyjádřena jako matematická funkce, která na základě délky vstupu určí časovou a paměťovou složitost výpočtu. Obvykle se pojem „analýza algoritmů“ používá pro teoretickou analýzu chování algoritmu v závislosti na velikosti dat, viz asymptotická složitost. Jiná činnost je měření charakteristik konkrétního procesu, např. při profilování. Analýza algoritmů je důležitá součást obecnější teorie složitosti, která poskytuje teoretické odhady potřebných zdrojů pro provedení jakéhokoli algoritmu, který řeší určitý . Tyto odhady mohou poskytnout užitečná vodítka pro hledání efektivních algoritmů. Jestliže chceme algoritmy analyzovat, potřebujeme jazyk pro popis algoritmů (zdrojový kód nebo pseudokód) a výpočetní model. Výsledkem analýzy je obvykle funkce, která poskytuje odhad doby, po kterou se bude daný algoritmus vykonávat. Jejím parametrem (n) je velikost vstupních dat. Doba běhu algoritmu v praxi závisí na mnoha faktorech. Je zřejmé, že výkonnější počítač při stejném vstupu provede daný algoritmus rychleji. Další úskalí spočívá v tom, jak se vlastně tento čas měří. Při opakování měření se může stát, že získáme rozdílné údaje doby běhu i pro zcela stejné vstupní hodnoty. Zvláště výrazný bývá tento rozdíl u malých časů. Výsledné hodnoty se proto počítají jako aritmetický průměr z několika měření. Praktické experimenty mají tato hlavní omezení: * Experimenty je možné z časového hlediska provést jen s určitým souborem dat. * Je těžké udělat porovnání dvou algoritmů – znamená to experimentovat za identických podmínek. * Je nutné algoritmus implementovat a provést experimenty – vyjádřit v nějakém programovacím jazyce. Analýza algoritmů je v praktické informatice velmi důležitá, protože použití neefektivního algoritmu může významně ovlivnit výkon a stabilitu systému. Například u aplikací, u kterých je důležitá rychlost, může dlouhé čekání na výsledek způsobit, že získaná data budou již zastaralá a zbytečná. Tento problém byl aktuální především v dobách, kdy počítače dosahovaly velmi omezených výkonů a strojový čas byl velmi drahý. (cs)
  • In computer science, the analysis of algorithms is the process of finding the computational complexity of algorithms – the amount of time, storage, or other resources needed to execute them. Usually, this involves determining a function that relates the length of an algorithm's input to the number of steps it takes (its time complexity) or the number of storage locations it uses (its space complexity). An algorithm is said to be efficient when this function's values are small, or grow slowly compared to a growth in the size of the input. Different inputs of the same length may cause the algorithm to have different behavior, so best, worst and average case descriptions might all be of practical interest. When not otherwise specified, the function describing the performance of an algorithm is usually an upper bound, determined from the worst case inputs to the algorithm. The term "analysis of algorithms" was coined by Donald Knuth. Algorithm analysis is an important part of a broader computational complexity theory, which provides theoretical estimates for the resources needed by any algorithm which solves a given computational problem. These estimates provide an insight into reasonable directions of search for efficient algorithms. In theoretical analysis of algorithms it is common to estimate their complexity in the asymptotic sense, i.e., to estimate the complexity function for arbitrarily large input. Big O notation, Big-omega notation and Big-theta notation are used to this end. For instance, binary search is said to run in a number of steps proportional to the logarithm of the length of the sorted list being searched, or in O(log(n)), colloquially "in logarithmic time". Usually asymptotic estimates are used because different implementations of the same algorithm may differ in efficiency. However the efficiencies of any two "reasonable" implementations of a given algorithm are related by a constant multiplicative factor called a hidden constant. Exact (not asymptotic) measures of efficiency can sometimes be computed but they usually require certain assumptions concerning the particular implementation of the algorithm, called model of computation. A model of computation may be defined in terms of an abstract computer, e.g., Turing machine, and/or by postulating that certain operations are executed in unit time.For example, if the sorted list to which we apply binary search has n elements, and we can guarantee that each lookup of an element in the list can be done in unit time, then at most log2 n + 1 time units are needed to return an answer. (en)
  • El análisis de algoritmos es una parte importante de la Teoría de complejidad computacional más amplia, que provee estimaciones teóricas para los recursos que necesita cualquier algoritmo que resuelva un problema computacional dado. Estas estimaciones resultan ser bastante útiles en la búsqueda de algoritmos eficientes. A la hora de realizar un análisis teórico de algoritmos es común calcular su complejidad en un sentido asintótico, es decir, para un tamaño de entrada suficientemente grande. La cota superior asintótica, y las notaciones omega (cota inferior) y theta (caso promedio) se usan con esa finalidad. Por ejemplo, la búsqueda binaria decimos que se ejecuta en una cantidad de pasos proporcional a un logaritmo, en O(log(n)), coloquialmente "en tiempo logarítmico". Normalmente las estimaciones asintóticas se utilizan porque diferentes implementaciones del mismo algoritmo no tienen por qué tener la misma eficiencia. No obstante la eficiencia de dos implementaciones "razonables" cualesquiera de un algoritmo dado están relacionadas por una constante multiplicativa llamada constante oculta. La medida exacta (no asintótica) de la eficiencia a veces puede ser computada pero para ello suele hacer falta aceptar supuestos acerca de la implementación concreta del algoritmo, llamada modelo de computación. Un modelo de computación puede definirse en términos de un ordenador abstracto, como la Máquina de Turing, y/o postulando que ciertas operaciones se ejecutan en una unidad de tiempo.Por ejemplo, si al conjunto ordenado al que aplicamos una búsqueda binaria tiene 'n' elementos, y podemos garantizar que una única búsqueda binaria puede realizarse en un tiempo unitario, entonces se requieren como mucho log2 N + 1 unidades de tiempo para devolver una respuesta. Las medidas exactas de eficiencia son útiles para quienes verdaderamente implementan y usan algoritmos, porque tienen más precisión y así les permite saber cuánto tiempo pueden suponer que tomará la ejecución. Para algunas personas, como los desarrolladores de videojuegos, una constante oculta puede significar la diferencia entre éxito y fracaso. Las estimaciones de tiempo dependen de cómo definamos un paso. Para que el análisis tenga sentido, debemos garantizar que el tiempo requerido para realizar un paso se encuentre acotado superiormente por una constante. Hay que mantenerse precavido en este terreno; por ejemplo, algunos análisis cuentan con que la suma de dos números se hace en un paso. Este supuesto puede no estar garantizado en ciertos contextos. Si por ejemplo los números involucrados en la computación pueden ser arbitrariamente grandes, dejamos de poder asumir que la adición requiere un tiempo constante (usando papel y lápiz, compara el tiempo que necesitas para sumar dos enteros de 2 dígitos cada uno y el necesario para hacerlo con dos enteros pero de 1000 dígitos cada uno). (es)
  • L'analyse de la complexité d'un algorithme consiste en l'étude formelle de la quantité de ressources (par exemple de temps ou d'espace) nécessaire à l'exécution de cet algorithme. Celle-ci ne doit pas être confondue avec la théorie de la complexité, qui elle étudie la difficulté intrinsèque des problèmes, et ne se focalise pas sur un algorithme en particulier. (fr)
  • アルゴリズム解析とは、アルゴリズムの実行に必要とされるリソース(時間や記憶領域)量を見積もることである。多くのアルゴリズムは任意長の入力を受け付けるよう設計されている。アルゴリズムの「効率」や「複雑さ」は一般に、入力長からそのアルゴリズムを実行するのに必要なステップ数(時間複雑性)や記憶領域サイズ(空間複雑性)への関数として表される。 アルゴリズム解析は計算複雑性理論の重要な一分野である。計算複雑性理論では、与えられた計算問題を解くアルゴリズムが必要とするリソースを理論的に見積もる。この見積もりにより効率的なアルゴリズムを設計する指針が得られることがある。 アルゴリズム解析ではふつう、漸近的(asymptotic)な意味で複雑性を見積もる。すなわち、ある程度大きな入力長の際の複雑性関数を見積もる。このためにO記法、Ω記法、Θ記法が用いられる。例えば、二分探索のステップ数は入力サイズの対数に比例し、これを O(log(n)) と表記したり、「対数時間」と称したりする。このような漸近的な見積もりを用いるのは、同じアルゴリズムでも実装の違いにより差が出るのを捨象するためである。異なる妥当な実装による効率の違いは定数倍に留まる。この定数を隠れた定数(hidden constant)と呼ぶ。 漸近的でない正確な効率がわかる場合もあるが、そのためには「計算モデル」と呼ばれるアルゴリズムの特定の実装を仮定する必要がある。計算モデルはチューリング機械のような抽象化された機械を使うか、個々の命令の実行時間が変化しないと仮定することが多い(例えば実際のコンピュータではキャッシュにヒットするかしないかでは大きく実行時間が異なるが、アルゴリズム解析では一般にそれを無視する)。例えば、二分探索で N 個のソートされた数から探索する場合、1回の参照を一定の単位時間でできるとした場合、回答を得るまでに最大で log2 N+1 単位時間を要する。 (ja)
  • 알고리즘 분석(영어: analysis of algorithms)은 컴퓨터 과학에서 알고리즘을 실행하는데 필요한 (시간과 기억 용량과 같은) 자원의 수를 결정하는 일을 가리킨다. 대부분의 알고리즘은 임의의 길이의 입력과 함께 동작하도록 구성된다. 일반적으로 알고리즘의 효율성과 실행 시간은 단계의 수 (시간 복잡도)와 기억 위치 (공간 복잡도)에 대한 입력 길이와 관련한 함수로 나타낼 수 있다. 알고리즘 분석이 더 광범위한 계산 복잡도 이론의 중요한 부분인데, 주어진 계산 문제를 해결하는 알고리즘에 필요한 자원에 대한 이론적 견적을 제공한다. 이러한 견적들은 효율적인 알고리즘을 검색하는데 도움을 준다. 알고리즘 분석에서는 보통 점근적(asymptotic) 의미로 복잡도를 계산한다. 즉, O표기법, Ω표기법, Θ표기법과 같은 방법으로 일정 크기의 입력 자료에 대한 복잡도 함수를 구한다. 예를 들어, 이진 탐색의 단계 수는 입력 자료의 크기에 대수적으로 비례하는데, 이것을 또는 이라 한다. 점근적인 방법을 사용하는 이유는, 같은 알고리즘이라도 입력 자료의 크기에 따라 수행 시간에 차이가 나는 것을 보완하기 위해서이다. 이런 수행 시간의 차이는 상수 배로 나타나는데, 이때의 상수를 숨은 상수(hidden constant)라고 한다. 시간 효율성의 추산은 수행 단계로서 정의하는 것에 의존한다. 의미있는 분석을 하려면, 각 단계에서 걸리는 수행 시간에 상한이 있어야 한다. 예를 들어, 두 수의 덧셈을 하나의 단계라 할 때, 각 수가 지극히 크면, 덧셈이 일정한 시간 내에 완료된다고 할 수 없기 때문이다. (2자리수의 덧셈을 하는 경우와 1000자리수의 덧셈을 하는 경우를 비교하여 생각해보라.) (ko)
  • Analiza algorytmu to sposób określenia zasobów, które są potrzebne w celu wykonania algorytmu: ilości czasu i miejsca w pamięci, szerokości pasma lub liczby układów logicznych. W analizie algorytmu czas działania algorytmu spełnia ważną rolę, ponieważ niektóre proste problemy mogą powodować niezwykle długie obliczenia. W analizie tej rozważa się przypadek najdłuższego czasu działania dla każdych danych wejściowych określonego rozmiaru oraz przypadek średniego czasu oczekiwania na działania danego algorytmu przy założeniu, iż wszystkie dane wejściowe określonego rozmiaru są jednakowo prawdopodobne. (pl)
  • Em ciência da computação, a análise de algoritmos tem como função determinar os recursos necessários para executar um dado algoritmo. A maior parte dos algoritmos são pensados para trabalhar com entradas (inputs) de tamanho arbitrário. Em geral, a eficiência ou complexidade de um algoritmo é função do tamanho do problema, do número de passos necessário (complexidade temporal) e da complexidade espacial ou de memória do sistema usado para executar o algoritmo. Esta disciplina faz parte da mais vasta teoria da complexidade computacional, que permite fazer estimativas quanto aos recursos necessários para que um algoritmo resolva um determinado problema computacional. Assim, o objetivo final não é apenas fazer códigos que funcionem, mas que sejam também eficientes. Para isso, deve-se estudar alguns tipos de problemas que podem ser resolvidos computacionalmente. Em seguida, deve ser visto como a abordagem adotada para resolver pode influenciar, levando a um algoritmo mais ou menos eficiente. "Ao verificar que um dado programa está muito lento, uma pessoa prática pede uma máquina mais rápida ao seu chefe. Mas o ganho potencial que uma máquina mais rápida pode proporcionar é tipicamente limitado por um fator de 10, por razões técnicas ou econômicas. Para obter um ganho maior, é preciso buscar melhores algoritmos. Um bom algoritmo, mesmo rodando em uma máquina lenta, sempre acaba derrotando (para instâncias grandes do problema) um algoritmo ruim rodando em uma máquina rápida. Sempre." (pt)
  • 在计算机科学中,算法分析(英語:Analysis of algorithm)是分析执行一个给定算法需要消耗的计算资源数量(例如计算时间,存储器使用等)的过程。算法的效率或复杂度在理论上表示为一个函数。其定义域是输入数据的长度(通常考虑任意大的输入,没有上界),值域通常是执行步骤数量(时间复杂度)或者存储器位置数量(空间复杂度)。算法分析是计算复杂度理论的重要组成部分。 理论分析常常利用渐近分析估计一个算法的复杂度,并使用大O符号、大Ω符号和大Θ符号作为标记。举例,二分查找所需的执行步骤数量与查找列表的长度之对数成正比,记为 ,简称为「对数时间」。通常使用渐近分析的原因是,同一算法的不同具体的效率可能有差别。但是,对于任何给定的算法,所有符合其设计者意图的实现,它们之间的性能差异应当仅仅是一个系数。 精确分析算法的效率有时也是可行的,但这样的分析通常需要一些与具体实现相关的假设,称为计算模型。计算模型可以用抽象机器来定义,比如图灵机。或者可以假设某些基本操作在单位时间内可完成。 假设二分查找的目标列表总共有 n 个元素。如果我们假设单次查找可以在一个时间单位内完成,那么至多只需要 单位的时间就可以得到结果。这样的分析在有些场合非常重要。 算法分析在实际工作中是非常重要的,因为使用低效率的算法会显著降低系统性能。在对运行时间要求极高的场合,耗时太长的算法得到的结果可能是过期或者无用的。低效率算法也会大量消耗计算资源。 (zh)
  • Аналіз алгоритмів — це процес визначення обчислювальної складності алгоритмів, тобто кількості часу, пам'яті чи інших ресурсів, необхідних для виконання алгоритмів. Як правило, це передбачає визначення функції, яка пов'язує розмір вхідних даних алгоритму з кількістю кроків виконання (його часовою складністю) або кількістю місця, що він використовує (його ). Алгоритм вважається ефективним, якщо значення цієї функції малі або зростають повільно у порівнянні зі збільшенням розміру вхідних даних. Різні входи однакової довжини можуть призводити до різної поведінки алгоритму, тому описи цих випадків можуть мати практичний інтерес. Якщо не вказано інше, функція, що описує складність алгоритму, зазвичай є верхньою межею, тобто, визначає його складність для найгірших випадків вхідних даних. Термін «аналіз алгоритмів» був введений Дональдом Кнутом. Аналіз алгоритмів є важливою частиною більш загальної теорії обчислювальної складності, яка встановлює теоретичні оцінки ресурсів, необхідних будь-якому алгоритму, що вирішує задану . Ці оцінки надають дослідникам розумні припущення щодо напрямків пошуку ефективних алгоритмів. У теоретичному аналізі алгоритмів їх часто оцінюють в асимптотично, тобто, оцінкою функції складності для довільно великих вхідних даних. Для цього використовуються нотації «О» великого, великих Омега і Тета. Наприклад, бінарний пошук виконується за кількість кроків, пропорційну логарифму довжини відсортованого списку, в якому ведеться пошук, або за O(log(n)), відоме як «логарифмічний час». Звичайно асимптотичні оцінки використовуються тому, що різні рішення однієї і тієї ж задачі можуть мати різну ефективність. Звичною є ситуація коли ефективність двох «розумних» реалізацій одного алгоритму можуть відрізнятися сталим множником, який називається прихованою сталою. Точні (не асимптотичні) вимірювання ефективності можуть бути обчислені, але потребують деяких припущень стосовно реалізації алгоритму, відомі як модель обчислення. Модель обчислення може бути визначена в термінах абстрактного комп'ютера, такого як машина Тьюрінга, також в ній визначається час виконання кожної операції або робиться припущення, що всі операції виконуються за однаковий час. Наприклад, якщо відсортований список, до якого застосовується бінарний пошук, має n елементів, а також вважаємо, що кожна операція зчитування елемента списку виконується за якусь сталу одиницю часу, тоді, для отримання результату потрібно максимум log2 n + 1 одиниць часу. (uk)
dbo:wikiPageExternalLink
dbo:wikiPageID
  • 2230 (xsd:integer)
dbo:wikiPageLength
  • 25732 (xsd:integer)
dbo:wikiPageRevisionID
  • 982884184 (xsd:integer)
dbo:wikiPageWikiLink
dbp:wikiPageUsesTemplate
dct:subject
rdf:type
rdfs:comment
  • تحليل الخوارزميات هو تحديد مقدار الموارد (Resources) (مثل الوقت وسعة التخزين) اللازمة لتنفيذ هذه الخوارزمية. معظم الخوارزميات تصمم للعمل مع مدخلات مطلقة الطول. عادة كفاءة والتعقيد لخوارزمية يتحدد كدالة تتبع إلى عدد الخطوات (تعقيد الوقت time complexity) أو أماكن التخزين (تعقيد المكان space complexity) تحليل الخوارزميات جزء مهم من نظرية التعقيد الحسابي لأنها تؤمن تقدير نظري للموارد اللازمة من أجل إنجاز خوارزمية لحل مسألة تحسبيبة. (ar)
  • L'analyse de la complexité d'un algorithme consiste en l'étude formelle de la quantité de ressources (par exemple de temps ou d'espace) nécessaire à l'exécution de cet algorithme. Celle-ci ne doit pas être confondue avec la théorie de la complexité, qui elle étudie la difficulté intrinsèque des problèmes, et ne se focalise pas sur un algorithme en particulier. (fr)
  • L'anàlisi d'algorismes és una part important de la teoria de complexitat computacional més àmplia, que proveeix estimacions teòriques per als recursos que necessita qualsevol algorisme que resolgui un problema computacional donat. Aquestes estimacions resulten ser bastant útils en la recerca d'algorismes eficients. (ca)
  • Analýza algoritmů je v matematické informatice určení rozsahu výpočetních prostředků potřebných k vykonání algoritmu. Jako primární kritéria náročnosti algoritmu se volí doba běhu a použitý paměťový prostor. Většina algoritmů je navržena tak, že mohou přijímat vstup o libovolné délce. Nákladnost (složitost) algoritmu je obvykle vyjádřena jako matematická funkce, která na základě délky vstupu určí časovou a paměťovou složitost výpočtu. (cs)
  • In computer science, the analysis of algorithms is the process of finding the computational complexity of algorithms – the amount of time, storage, or other resources needed to execute them. Usually, this involves determining a function that relates the length of an algorithm's input to the number of steps it takes (its time complexity) or the number of storage locations it uses (its space complexity). An algorithm is said to be efficient when this function's values are small, or grow slowly compared to a growth in the size of the input. Different inputs of the same length may cause the algorithm to have different behavior, so best, worst and average case descriptions might all be of practical interest. When not otherwise specified, the function describing the performance of an algorithm i (en)
  • El análisis de algoritmos es una parte importante de la Teoría de complejidad computacional más amplia, que provee estimaciones teóricas para los recursos que necesita cualquier algoritmo que resuelva un problema computacional dado. Estas estimaciones resultan ser bastante útiles en la búsqueda de algoritmos eficientes. (es)
  • アルゴリズム解析とは、アルゴリズムの実行に必要とされるリソース(時間や記憶領域)量を見積もることである。多くのアルゴリズムは任意長の入力を受け付けるよう設計されている。アルゴリズムの「効率」や「複雑さ」は一般に、入力長からそのアルゴリズムを実行するのに必要なステップ数(時間複雑性)や記憶領域サイズ(空間複雑性)への関数として表される。 アルゴリズム解析は計算複雑性理論の重要な一分野である。計算複雑性理論では、与えられた計算問題を解くアルゴリズムが必要とするリソースを理論的に見積もる。この見積もりにより効率的なアルゴリズムを設計する指針が得られることがある。 アルゴリズム解析ではふつう、漸近的(asymptotic)な意味で複雑性を見積もる。すなわち、ある程度大きな入力長の際の複雑性関数を見積もる。このためにO記法、Ω記法、Θ記法が用いられる。例えば、二分探索のステップ数は入力サイズの対数に比例し、これを O(log(n)) と表記したり、「対数時間」と称したりする。このような漸近的な見積もりを用いるのは、同じアルゴリズムでも実装の違いにより差が出るのを捨象するためである。異なる妥当な実装による効率の違いは定数倍に留まる。この定数を隠れた定数(hidden constant)と呼ぶ。 (ja)
  • 알고리즘 분석(영어: analysis of algorithms)은 컴퓨터 과학에서 알고리즘을 실행하는데 필요한 (시간과 기억 용량과 같은) 자원의 수를 결정하는 일을 가리킨다. 대부분의 알고리즘은 임의의 길이의 입력과 함께 동작하도록 구성된다. 일반적으로 알고리즘의 효율성과 실행 시간은 단계의 수 (시간 복잡도)와 기억 위치 (공간 복잡도)에 대한 입력 길이와 관련한 함수로 나타낼 수 있다. 알고리즘 분석이 더 광범위한 계산 복잡도 이론의 중요한 부분인데, 주어진 계산 문제를 해결하는 알고리즘에 필요한 자원에 대한 이론적 견적을 제공한다. 이러한 견적들은 효율적인 알고리즘을 검색하는데 도움을 준다. 시간 효율성의 추산은 수행 단계로서 정의하는 것에 의존한다. 의미있는 분석을 하려면, 각 단계에서 걸리는 수행 시간에 상한이 있어야 한다. 예를 들어, 두 수의 덧셈을 하나의 단계라 할 때, 각 수가 지극히 크면, 덧셈이 일정한 시간 내에 완료된다고 할 수 없기 때문이다. (2자리수의 덧셈을 하는 경우와 1000자리수의 덧셈을 하는 경우를 비교하여 생각해보라.) (ko)
  • Analiza algorytmu to sposób określenia zasobów, które są potrzebne w celu wykonania algorytmu: ilości czasu i miejsca w pamięci, szerokości pasma lub liczby układów logicznych. W analizie algorytmu czas działania algorytmu spełnia ważną rolę, ponieważ niektóre proste problemy mogą powodować niezwykle długie obliczenia. (pl)
  • Em ciência da computação, a análise de algoritmos tem como função determinar os recursos necessários para executar um dado algoritmo. A maior parte dos algoritmos são pensados para trabalhar com entradas (inputs) de tamanho arbitrário. Em geral, a eficiência ou complexidade de um algoritmo é função do tamanho do problema, do número de passos necessário (complexidade temporal) e da complexidade espacial ou de memória do sistema usado para executar o algoritmo. Esta disciplina faz parte da mais vasta teoria da complexidade computacional, que permite fazer estimativas quanto aos recursos necessários para que um algoritmo resolva um determinado problema computacional. (pt)
  • Аналіз алгоритмів — це процес визначення обчислювальної складності алгоритмів, тобто кількості часу, пам'яті чи інших ресурсів, необхідних для виконання алгоритмів. Як правило, це передбачає визначення функції, яка пов'язує розмір вхідних даних алгоритму з кількістю кроків виконання (його часовою складністю) або кількістю місця, що він використовує (його ). Алгоритм вважається ефективним, якщо значення цієї функції малі або зростають повільно у порівнянні зі збільшенням розміру вхідних даних. Різні входи однакової довжини можуть призводити до різної поведінки алгоритму, тому описи цих випадків можуть мати практичний інтерес. Якщо не вказано інше, функція, що описує складність алгоритму, зазвичай є верхньою межею, тобто, визначає його складність для найгірших випадків вхідних даних. (uk)
  • 在计算机科学中,算法分析(英語:Analysis of algorithm)是分析执行一个给定算法需要消耗的计算资源数量(例如计算时间,存储器使用等)的过程。算法的效率或复杂度在理论上表示为一个函数。其定义域是输入数据的长度(通常考虑任意大的输入,没有上界),值域通常是执行步骤数量(时间复杂度)或者存储器位置数量(空间复杂度)。算法分析是计算复杂度理论的重要组成部分。 理论分析常常利用渐近分析估计一个算法的复杂度,并使用大O符号、大Ω符号和大Θ符号作为标记。举例,二分查找所需的执行步骤数量与查找列表的长度之对数成正比,记为 ,简称为「对数时间」。通常使用渐近分析的原因是,同一算法的不同具体的效率可能有差别。但是,对于任何给定的算法,所有符合其设计者意图的实现,它们之间的性能差异应当仅仅是一个系数。 精确分析算法的效率有时也是可行的,但这样的分析通常需要一些与具体实现相关的假设,称为计算模型。计算模型可以用抽象机器来定义,比如图灵机。或者可以假设某些基本操作在单位时间内可完成。 假设二分查找的目标列表总共有 n 个元素。如果我们假设单次查找可以在一个时间单位内完成,那么至多只需要 单位的时间就可以得到结果。这样的分析在有些场合非常重要。 (zh)
rdfs:label
  • Analysis of algorithms (en)
  • تحليل الخوارزميات (ar)
  • Anàlisi d'algorismes (ca)
  • Analýza algoritmů (cs)
  • Análisis de algoritmos (es)
  • Analyse de la complexité des algorithmes (fr)
  • アルゴリズム解析 (ja)
  • 알고리즘 분석 (ko)
  • Analiza algorytmów (pl)
  • Análise de algoritmos (pt)
  • Аналіз алгоритмів (uk)
  • 算法分析 (zh)
owl:sameAs
prov:wasDerivedFrom
foaf:isPrimaryTopicOf
is dbo:academicDiscipline of
is dbo:knownFor of
is dbo:wikiPageDisambiguates of
is dbo:wikiPageRedirects of
is dbo:wikiPageWikiLink of
is dbp:field of
is dbp:knownFor of
is foaf:primaryTopic of