Функцияның шекті мінез-құлқы және Big O нотациясы

Кіріспе

Функцияның шектейтін мінез-құлқын сипаттайды. Үлкен O белгісі – аргументі белгілі бір мәнге немесе шексіздікке жақындағанда функцияның шектейтін мінез-құлқын сипаттайтын математикалық белгі. Үлкен O – неміс математигі Пол Бахманн жасаған белгілер отбасының бір мүшесі. Аналитикалық сандар теориясында Үлкен O белгісі көбінесе арифметикалық функция мен жақсы түсінілген жуықтама арасындағы айырманы бағалау үшін қолданылады; мұндай айырманың белгілі бір мысалы – жай сандар теоремасындағы қалдық мүше. Үлкен O белгісі көптеген басқа салаларда да ұқсас бағалаулар беру үшін қолданылады. Үлкен O белгісі функцияларды олардың өсу жылдамдықтары бойынша сипаттайды: бірдей асимптотикалық өсу жылдамдығына ие әртүрлі функциялар бірдей O белгісімен көрсетілуі мүмкін. O әрпі қолданылады, себебі функцияның өсу жылдамдығы функцияның реті деп те аталады. Функцияны Үлкен O белгісі арқылы сипаттау, әдетте функцияның өсу жылдамдығының жоғарғы шегін ғана көрсетеді. Үлкен O белгісімен байланысты бірнеше туыс белгілер бар, олар o, Ω, ω және Θ символдары арқылы асимптотикалық өсу жылдамдықтарының басқа да шектерін сипаттау үшін қолданылады.

Тең белгі

Жоғарыда анықталған "f(x) O(g(x))" мәлімдемесі әдетте 1=f(x) = O(g(x)) деп жазылады. Кейбіреулер мұны белгілерді дұрыс емес пайдалану деп санайды, өйткені тең белгісін қолдану шатастыруға болады, себебі бұл мәлімдемеде жоқ симметрияны білдіреді. Де Брюйн айтқандай, 1=O(x) = O(x²) дұрыс, бірақ 1=O(x²) = O(x) дұрыс емес. Кнут мұндай мәлімдемелерді "бір жақты теңдіктер" деп сипаттайды, өйткені егер жақтарын ауыстыруға болатын болса, "біз 1=n = n² сияқты абсурдтық нәрселерді 1=n = O(n²) және 1=n² = O(n²) теңдіктерінен шығаруға болады". Басқа хатта Кнут "теңдік белгісі мұндай жазбаларға қатысты симметриялы емес" деп көрсеткен, себебі бұл жазбада "математиктер әдетте = белгісін ағылшын тіліндегі "is" сөзін қолданғандай қолданады: Аристотель – адам, бірақ әр адам міндетті түрде Аристотель емес". Осы себептерге байланысты, жиынтық белгісін қолданып, f(x) ∈ O(g(x)) деп жазу (осылай оқылады: "f(x) O(g(x)) жиынтығының мүшесі" немесе "f(x) O(g(x)) жиынтығында орналасқан"), O(g(x)) барлық функциялар класы ретінде қарастырылады, мұнда |h(x)| ≤ Cg(x) шарты орындалады, C – кез келген оң нақты сан. TeX жүйесінде бұл математикалық режимде O әрпін жазу арқылы жасалады. Грек тіліндегі Бахманн-Ландау белгілерінен айырмашылығы, оған ерекше символ қажет емес. Дегенмен, кейбір авторлар оның орнына каллиграфиялық түрін қолданады.

Ортақ функциялар реті

Мұнда алгоритмнің жұмыс уақытын талдау кезінде жиі кездесетін функциялардың сыныптарының тізімі берілген. Әр жағдайда c – оң тұрақты, ал n шексіз өседі. Әдетте, баяу өсетін функциялар бірінші болып тізіледі.

Here is a list of classes of functions that are commonly encountered when analyzing the running time of an algorithm. In each case, c is a positive constant and n increases without bound. The slower growing functions are generally listed first. Notation Name Example constant Finding the median value for a sorted array of numbers; Calculating ; Using a constant size lookup table double logarithmic Average number of comparisons spent finding an item using interpolation search in a sorted array of uniformly distributed values logarithmic Finding an item in a sorted array with a binary search or a balanced search tree as well as all operations in a binomial heap polylogarithmic Matrix chain ordering can be solved in polylogarithmic time on a parallel random access machine. fractional power Searching in a k d tree linear Finding an item in an unsorted list or in an unsorted array; adding two n bit integers by ripple carry n log star n Performing triangulation of a simple polygon using Seidel's algorithm, where linearithmic, loglinear, quasilinear, or "n log n" Performing a fast Fourier transform; fastest possible comparison sort; heapsort and merge sort quadratic Multiplying two n digit numbers by schoolbook multiplication; simple sorting algorithms, such as bubble sort, selection sort and insertion sort; (worst case) bound on some usually faster sorting algorithms such as quicksort, Shellsort, and tree sort polynomial or algebraic Tree adjoining grammar parsing; maximum matching for bipartite graphs; finding the determinant with LU decomposition L notation or sub exponential Factoring a number using the quadratic sieve or number field sieve exponential Finding the (exact) solution to the travelling salesman problem using dynamic programming; determining if two logical statements are equivalent using brute force search factorial Solving the travelling salesman problem via brute force search; generating all unrestricted permutations of a poset; finding the determinant with Laplace expansion; enumerating all partitions of a set
The statement is sometimes weakened to to derive simpler formulas for asymptotic complexity. For any and , is a subset of for any , so may be considered as a polynomial with some bigger order.

Атауы | Мысал | Тұрақты
------- | -------- | --------
тұрақты | Сорталған сандар массиві үшін медиананы табу; Есептеу; Тұрақты өлшемді іздеу кестесін пайдалану |
қос логарифмдік | Біркелкі таралған мәндердің сұрыпталған массивінде интерполяциялық іздеуді қолдану арқылы элементті табуға жұмсалған салыстырулардың орташа саны |
логарифмдік | Екілік іздеу немесе теңгерілген іздеу ағашы бар сұрыпталған массивтен элементті табу, сондай-ақ биномиалдық үйірмедегі барлық операциялар |
полилогарифмдік | Матрица тізбегін реттеуді параллель кездейсоқ қолжетімділік машинасында полилогарифмдік уақытта шешуге болады |
бөлшек дәрежелі | k d ағашында іздеу |
сызықтық | Сорталмаған тізімде немесе сұрыпталмаған массивте элементті табу; екі n биттік бүтін санды толқынды қосу |
n log* n | Сейдель алгоритмін қолдана отырып қарапайым көпбұрышты үшбұрыштау |
сызықтық-логарифмдік, лог-сызықтық, квазисызықтық немесе "n log n" | Жылдам Фурье түрлендіруін орындау; ең жылдам салыстыру сұрыптау; үйірмелік сұрыптау және біріктіру сұрыптау |
квадраттық | Екі n цифрлы санды мектептік көбейту арқылы көбейту; қарапайым сұрыптау алгоритмдері, мысалы, көпіршік сұрыптау, таңдау сұрыптау және енгізу сұрыптау; (ең нашар жағдайда) жылдам сұрыптау, Shellsort және ағаш сұрыптау сияқты әдетте жылдам сұрыптау алгоритмдерінің шегі |
полиномдық немесе алгебралық | Ағаш тіркесетін грамматиканы талдау; екібөлікті графтар үшін максималды сәйкестік табу; LU ыдырауымен анықтағышты табу |
L белгісі немесе экспоненциалды емес | Квадраттық елеуіш немесе сан өрісі елеуішін қолдана отырып санды жіктеу |
экспоненциалдық | Динамикалық бағдарламалауды қолдана отырып саяхатшының мәселесіне нақты шешім табу; күшпен іздеуді қолдана отырып екі логикалық тұжырымның эквивалентті екенін анықтау |
факториалдық | Күшпен іздеуді қолдана отырып саяхатшының мәселесін шешу; реттілік жиынтығының барлық шектеусіз өзгерістерін жасау; Лаплас кеңеюімен анықтағышты табу; жиынтықтың барлық бөлімдерін санау |

Кейде формуласын жеңілдету үшін формуласына дейін әлсіретеді. Кез келген және үшін, кез келген үшін ішкі жиыны болып табылады, сондықтан оны үлкен дәрежелі полином ретінде қарастыруға болады.

Қатынасты асимптотикалық белгілер

Үлкен О компьютерлік ғылымда кеңінен қолданылады. Осыған ұқсас тағы бірнеше белгілермен бірге, ол Бахманн-Ландау нотацияларының отбасын құрайды.

Кнут анықтамасы

1976 жылы Дональд Кнут күштірек қасиетті сипаттау үшін таңбасын пайдалануын негіздеу мақсатында мақала жариялады.

Жалпылау және онымен байланысты қолданыстар

Нормаланған векторлық кеңістікте мәндерді қабылдайтын функцияларға жалпылау оңай (абсолюттік шамаларды нормалармен алмастыру арқылы), мұнда f және g функциялары мәндерін бірдей кеңістікте қабылдауы міндетті емес. Кез келген топологиялық топта мәндерді қабылдайтын g функцияларына да жалпылау мүмкін. "Шектелу процесі" x → xo кез келген сүзгі базасын енгізу арқылы, яғни f және g бағытталған торларына дейін жалпылауға болады. "o" белгісі туындыларды және дифференциалдануды өте жалпы кеңістіктерде анықтау үшін, сондай-ақ функциялардың (асимптотикалық) эквиваленттігін анықтау үшін қолданылады, бұл эквиваленттілік қатынасы және жоғарыдағы "f – Θ(g)" қатынасынан гөрі тар ұғым. (Егер f және g оң нақты мәнді функциялар болса, онда ол lim f / g = 1-ге дейін кемиді.) Мысалы, 2x – Θ(x), бірақ 1 = 2x – x – o(x) емес.

Тарих (Бахман Ландау, Харди және Виноградов белгілері)

O символын алғаш рет сан теориясымен айналысатын Пол Бахман 1894 жылы өзінің "Аналитическая Zahlentheorie" ("аналитикалық сан теориясы") атты кітабының екінші томында енгізді. Сан теориясымен айналысатын Эдмунд Ландау оны қабылдап, 1909 жылы о белгісін енгізуге шабыттанды; осылайша, екеуі де қазір Ландау белгілері деп аталады. Бұл белгілер 1950 жылдары қолданбалы математикада асимптотикалық талдау үшін қолданылды. ( "о" емес деген мағынада) символын 1914 жылы Харди мен Литтлвуд енгізді. Символ, бұрын түрлі мағыналарда қолданылған болса да, Харди 1910 жылы оны қолданды. Хардидің трактатында сол бетте жоғарыда символ анықталды, мұнда екі де орындалады дегенді білдіреді. Бұл жазу әлі күнге дейін аналитикалық сан теориясында қолданылады. Харди трактатында ол символді де ұсынды, мұнда белгілі бір тұрақты үшін орындалады. 1970 жылдары Дональд Кнут компьютерлік ғылымда үлкен O-ны танымал етті, ол Хардидің , және Харди мен Литтлвуд Омега белгісі үшін басқа анықтама ұсынды. Ресейлік сан теориясымен айналысатын Иван Матвеевич Виноградов өз белгісін енгізді, ол сан теориясында белгісінің орнына жиі қолданылады. Бізде және екі белгі де бір мақалада жиі қолданылады. Үлкен O бастапқыда "рет" ("Ordnung", Bachmann 1894) дегенді білдіреді, сондықтан ол латын әрпі. Бахман да, Ландау да оны "Омикрон" деп атаған жоқ. Символ кейінірек (1976) Кнутпен үлкен омикрон ретінде қарастырылды, бұл, мүмкін, оның Омега символының анықтамасына сілтеме жасады. Сан нөлді пайдалануға болмайды.