| dbo:abstract
|
- L-notation is an asymptotic notation analogous to big-O notation, denoted as for a bound variable tending to infinity. Like big-O notation, it is usually used to roughly convey the rate of growth of a function, such as the computational complexity of a particular algorithm. (en)
- La notation L est un analogue aux notations de Landau en notation asymptotique. Cette notation a été introduite par Carl Pomerance en 1982 pour comparer différents algorithmes de factorisation et a été généralisée à deux paramètres par Arjen Lenstra et Hendrik Lenstra. Elle est principalement utilisée en théorie algorithmique des nombres, où elle permet de donner une échelle entre les différents algorithmes exponentiels. En effet représente les fonctions polynomiales de ln (n) de degré c, et les fonctions exponentielles en la taille de l’entrée (ici, la taille est prise comme étant ), ce qui est le cas pour la représentation binaire des nombres), donc représente les fonctions polynomiales de n de degré c. (fr)
- La notazione L è una notazione asintotica analoga alla notazione O-grande, denotata come per una variabile limitata tendente a infinito. Come la notazione O-grande, è usata di solito per rendere in maniera approssimativa la complessità computazionale di un particolare algoritmo. Essa è definita come dove c è una costante positiva, e è una costante . La notazione L si usa principalmente nella teoria computazionale dei numeri, per esprimere la complessità degli algoritmi per i problemi difficili della teoria dei numeri, ad es. per la fattorizzazione degli interi e per i metodi di soluzione dei logaritmi discreti. Il beneficio di questa notazione è che semplifica l'analisi di questi logaritmi. La esprime il termine dominante, e la copre tutto ciò che è minore. Quando è 0, allora è una funzione polinomiale di ln n; quando è 1, allora è una funzione completamente esponenziale di ln n (e quindi polinomiale in n). Se è compreso tra 0 e 1, la funzione è subesponenziale (e superpolinomiale). (it)
- A notação L é uma notação assintótica análoga à notação O grande, denotada como para uma variável limitada tendendo ao infinito. Como a notação O grande, geralmente é usada para transmitir aproximadamente a complexidade computacional de um algoritmo específico. (pt)
- L-нотація — це асимптотична нотація, аналогічна до О-нотації, записується як при , що прямує до нескінченності. Подібно до O-великого, L-нотація зазвичай використовується при оцінці обчислювальної складності алгоритмів. При цьому є деяким параметром вхідних даних алгоритму, пропорційним їх розміру: наприклад, число вершин і ребер у вхідному графі в алгоритмах пошуку найкоротшого шляху, або натуральне число в алгоритмах розкладання його на прості множники. Перевага цієї нотації над нотацією O-великого полягає в тому, що вона спрощує аналіз цих алгоритмів. (uk)
- L-нотация — это асимптотическая нотация, аналогичная О-нотации, записывается как для стремящимся к бесконечности. Подобно O-большому, L-нотация обычно используется для приближённой оценки вычислительной сложности конкретного алгоритма. При этом представляет собой некоторый параметр входных данных алгоритма, пропорциональный их размеру: например, число вершин и рёбер во входном графе в алгоритмах поиске в нём кратчайшего пути, или натуральное число в алгоритмах разложении его на простые сомножители. определяется формулой , где — положительная константа, а — константа . L-нотация используется в основном в вычислительной теории чисел для выражения сложности алгоритмов для трудных проблем теории чисел, например, алгоритмов решета разложения натуральных чисел на простые сомножители и методов вычисления дискретных логарифмов. Преимущество такой нотации заключается в упрощении анализа алгоритмов. Сомножитель в отражает доминирующую составляющую, а сомножитель относится ко всему менее значительному. При этом, когда равна 0, является многочленом от ln n, в то время как при равном 1, является экспонентой от ln n (и, поэтому, полиномом от n). Если же находится где-то между 0 и 1, то функция субэкспоненциальная, т. е. растёт медленнее, чем экспоненциальная функция с основанием больше 1 (или сверх-полиномиальная). (ru)
- L符號是個類似大O符號的漸近符號，標記為，多用於表示特定演算法的計算複雜性。 (zh)
|
| rdfs:comment
|
- L-notation is an asymptotic notation analogous to big-O notation, denoted as for a bound variable tending to infinity. Like big-O notation, it is usually used to roughly convey the rate of growth of a function, such as the computational complexity of a particular algorithm. (en)
- La notation L est un analogue aux notations de Landau en notation asymptotique. Cette notation a été introduite par Carl Pomerance en 1982 pour comparer différents algorithmes de factorisation et a été généralisée à deux paramètres par Arjen Lenstra et Hendrik Lenstra. Elle est principalement utilisée en théorie algorithmique des nombres, où elle permet de donner une échelle entre les différents algorithmes exponentiels. En effet représente les fonctions polynomiales de ln (n) de degré c, et les fonctions exponentielles en la taille de l’entrée (ici, la taille est prise comme étant ), ce qui est le cas pour la représentation binaire des nombres), donc représente les fonctions polynomiales de n de degré c. (fr)
- A notação L é uma notação assintótica análoga à notação O grande, denotada como para uma variável limitada tendendo ao infinito. Como a notação O grande, geralmente é usada para transmitir aproximadamente a complexidade computacional de um algoritmo específico. (pt)
- L-нотація — це асимптотична нотація, аналогічна до О-нотації, записується як при , що прямує до нескінченності. Подібно до O-великого, L-нотація зазвичай використовується при оцінці обчислювальної складності алгоритмів. При цьому є деяким параметром вхідних даних алгоритму, пропорційним їх розміру: наприклад, число вершин і ребер у вхідному графі в алгоритмах пошуку найкоротшого шляху, або натуральне число в алгоритмах розкладання його на прості множники. Перевага цієї нотації над нотацією O-великого полягає в тому, що вона спрощує аналіз цих алгоритмів. (uk)
- L符號是個類似大O符號的漸近符號，標記為，多用於表示特定演算法的計算複雜性。 (zh)
- La notazione L è una notazione asintotica analoga alla notazione O-grande, denotata come per una variabile limitata tendente a infinito. Come la notazione O-grande, è usata di solito per rendere in maniera approssimativa la complessità computazionale di un particolare algoritmo. Essa è definita come dove c è una costante positiva, e è una costante . Quando è 0, allora è una funzione polinomiale di ln n; quando è 1, allora è una funzione completamente esponenziale di ln n (e quindi polinomiale in n). Se è compreso tra 0 e 1, la funzione è subesponenziale (e superpolinomiale). (it)
- L-нотация — это асимптотическая нотация, аналогичная О-нотации, записывается как для стремящимся к бесконечности. Подобно O-большому, L-нотация обычно используется для приближённой оценки вычислительной сложности конкретного алгоритма. При этом представляет собой некоторый параметр входных данных алгоритма, пропорциональный их размеру: например, число вершин и рёбер во входном графе в алгоритмах поиске в нём кратчайшего пути, или натуральное число в алгоритмах разложении его на простые сомножители. определяется формулой , где — положительная константа, а — константа . (ru)
|
