Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
Алгоритмді орындау үшін қажетті ресурстардың мөлшері
Amount of resources to perform an algorithm
Компьютерлік ғылымда алгоритмнің есептеу күрделілігі немесе жай ғана күрделілігі – оны іске қосу үшін қажетті ресурстардың мөлшері. Ерекше назар есептеу уақытына (әдетте қажетті элементарлық операциялар санымен өлшенеді) және жад сақтау талаптарына беріледі. Мәселенің күрделілігі – мәселені шешуге мүмкіндік беретін ең жақсы алгоритмдердің күрделілігі. Нақты берілген алгоритмдердің күрделілігін зерттеу алгоритмдерді талдау деп аталады, ал мәселелердің күрделілігін зерттеу – есептеу күрделілігі теориясы деп аталады. Екі сала да тығыз байланысты, себебі алгоритмнің күрделілігі әрқашан осы алгоритммен шешілетін мәселенің күрделілігінің жоғарғы шегі болып табылады. Сонымен қатар, тиімді алгоритмдерді жобалау үшін белгілі бір алгоритмнің күрделілігін шешілетін мәселенің күрделілігімен салыстыру маңызды. Көп жағдайда мәселенің күрделілігі туралы білген жалғыз нәрсе – ол ең тиімді белгілі алгоритмдердің күрделілігінен төмен. Сондықтан алгоритмдерді талдау және күрделілік теориясы арасында үлкен байланыс бар. Алгоритмді іске қосу үшін қажетті ресурстардың мөлшері әдетте кіріс мөлшеріне байланысты өзгеретіндіктен, күрделілік әдетте n → f(n) функциясы түрінде көрсетіледі, мұнда n – кіріс мөлшері, ал f(n) – ең нашар жағдайдың күрделілігі (n өлшемді барлық кірістер үшін қажетті ресурстардың максималды мөлшері) немесе орташа жағдайдың күрделілігі (n өлшемді барлық кірістер үшін ресурстардың орташа мөлшері). Уақыт күрделілігі әдетте n өлшемді кіріс үшін қажетті элементарлық операциялар саны ретінде көрсетіледі, мұнда элементарлық операциялар берілген компьютерде тұрақты уақыт алады және басқа компьютерде орындалғанда тек тұрақты фактормен өзгереді деп есептеледі. Ғарыштық күрделілік әдетте n өлшемді кірісте алгоритмге қажетті жад мөлшері ретінде көрсетіледі.
In computer science, the computational complexity or simply complexity of an algorithm is the amount of resources required to run it. Particular focus is given to computation time (generally measured by the number of needed elementary operations) and memory storage requirements. The complexity of a problem is the complexity of the best algorithms that allow solving the problem. The study of the complexity of explicitly given algorithms is called analysis of algorithms, while the study of the complexity of problems is called computational complexity theory. Both areas are highly related, as the complexity of an algorithm is always an upper bound on the complexity of the problem solved by this algorithm. Moreover, for designing efficient algorithms, it is often fundamental to compare the complexity of a specific algorithm to the complexity of the problem to be solved. Also, in most cases, the only thing that is known about the complexity of a problem is that it is lower than the complexity of the most efficient known algorithms. Therefore, there is a large overlap between analysis of algorithms and complexity theory. As the amount of resources required to run an algorithm generally varies with the size of the input, the complexity is typically expressed as a function n → f(n), where n is the size of the input and f(n) is either the worst case complexity (the maximum of the amount of resources that are needed over all inputs of size n) or the average case complexity (the average of the amount of resources over all inputs of size n). Time complexity is generally expressed as the number of required elementary operations on an input of size n, where elementary operations are assumed to take a constant amount of time on a given computer and change only by a constant factor when run on a different computer. Space complexity is generally expressed as the amount of memory required by an algorithm on an input of size n.
Уақыт
Ең көп қарастырылатын ресурс – уақыт. "Күрделілік" термині ешқандай шектеусіз қолданылғанда, көбінесе уақыт күрделілігін білдіреді. Күрделілік теориясында уақыттың әдеттегі өлшемдері (секундтар, минуттар сияқты) қолданылмайды, себебі олар нақты бір компьютер таңдауына және технологияның өркендеуіне тым тәуелді. Мысалы, қазіргі компьютер 1960 жылдардағы компьютерге қарағанда алгоритмді едәуір жылдам орындай алады; алайда, бұл алгоритмнің ішкі қасиеті емес, компьютерлік аппараттық құралдардағы технологиялық прогрестің нәтижесі. Күрделілік теориясы алгоритмдердің ішкі уақыт талаптарын, яғни алгоритмнің кез келген компьютерде тудыратын негізгі уақыт шектеулерін анықтауға бағытталған. Бұл есептеу барысында орындалатын элементарлық операциялардың санын санау арқылы қол жеткізіледі. Бұл операциялар белгілі бір машинада тұрақты уақытқа ие деп есептеледі (яғни, кіріс мөлшеріне тәуелді емес) және көбінесе қадамдар деп аталады.
The resource that is most commonly considered is time. When "complexity" is used without qualification, this generally means time complexity. The usual units of time (seconds, minutes etc.) are not used in complexity theory because they are too dependent on the choice of a specific computer and on the evolution of technology. For instance, a computer today can execute an algorithm significantly faster than a computer from the 1960s; however, this is not an intrinsic feature of the algorithm but rather a consequence of technological advances in computer hardware. Complexity theory seeks to quantify the intrinsic time requirements of algorithms, that is, the basic time constraints an algorithm would place on any computer. This is achieved by counting the number of elementary operations that are executed during the computation. These operations are assumed to take constant time (that is, not affected by the size of the input) on a given machine, and are often called steps.
Бит күрделілігі
Біт күрделілігі – алгоритмді іске қосу үшін қажетті биттермен жасалатын операциялар саны. Көптеген есептеу модельдерінде ол уақыт күрделілігімен тұрақты шамаға дейін тең. Компьютерлерде машиналық сөздермен жасалатын операциялар саны да біт күрделілігіне пропорционалды. Демек, уақыт күрделілігі мен біт күрделілігі нақты есептеу модельдері үшін эквивалентті.
Formally, the bit complexity refers to the number of operations on bits that are needed for running an algorithm. With most models of computation, it equals the time complexity up to a constant factor. On computers, the number of operations on machine words that are needed is also proportional to the bit complexity. So, the time complexity and the bit complexity are equivalent for realistic models of computation.
Ғарыш
Тағы бір маңызды ресурс – алгоритмдерді іске қосу үшін қажетті компьютер жадының мөлшері.
Another important resource is the size of computer memory that is needed for running algorithms.
Байланыс
Бірнеше өзара әрекеттесетін тараптармен орындалатын таратылған алгоритмдер класы үшін ең маңызды ресурс – байланыс күрделілігі. Ол алгоритмді орындайтын тараптар арасындағы қажетті коммуникация мөлшері болып табылады.
For the class of distributed algorithms that are commonly executed by multiple, interacting parties, the resource that is of most interest is the communication complexity. It is the necessary amount of communication between the executing parties.
Басқалар
Арифметикалық операциялардың саны – жиі қолданылатын тағы бір ресурс. Мұндай жағдайда арифметикалық күрделілік туралы сөз болады. Егер есептеу барысында кездесетін сандардың екілік өрнектемесінің мөлшеріне жоғарғы шек белгілі болса, уақыт күрделілігі көбінесе арифметикалық күрделіліктің тұрақты көбейткіші болып табылады. Көптеген алгоритмдер үшін есептеу кезінде қолданылатын бүтін сандардың мөлшері шектелмеген, сондықтан арифметикалық операциялар тұрақты уақыт алады деп есептеудің қажеті жоқ. Сондықтан, уақыт күрделілігі, бұл контексте көбінесе бит күрделілігі деп аталады, арифметикалық күрделіліктен әлдеқайда артық болуы мүмкін. Мысалы, n×n бүтін сан матрицасының анықтамасын есептеудің арифметикалық күрделілігі, әдеттегі алгоритмдер үшін (Гаусс жою әдісі) шамалы. Осы алгоритмдердің бит күрделілігі n-ге қатысты экспоненциалды, себебі есептеу барысында коэффициенттердің мөлшері экспоненциалды түрде өсуі мүмкін. Алайда, егер бұл алгоритмдер көп модульді арифметикамен үйлестірілсе, бит күрделілігі [[жұмсақ O белгісіне]] дейін төмендетілуі мүмкін. Сорттау және іздеуде қарастырылатын ресурс көбінесе салыстырулар саны болып табылады. Деректер тиісінше ұйымдастырылған жағдайда, бұл уақыт күрделілігін бағалаудың жақсы тәсілі болып саналады.
The number of arithmetic operations is another resource that is commonly used. In this case, one talks of arithmetic complexity. If one knows an upper bound on the size of the binary representation of the numbers that occur during a computation, the time complexity is generally the product of the arithmetic complexity by a constant factor. For many algorithms the size of the integers that are used during a computation is not bounded, and it is not realistic to consider that arithmetic operations take a constant time. Therefore, the time complexity, generally called bit complexity in this context, may be much larger than the arithmetic complexity. For example, the arithmetic complexity of the computation of the determinant of a n×n integer matrix is for the usual algorithms (Gaussian elimination). The bit complexity of the same algorithms is exponential in n, because the size of the coefficients may grow exponentially during the computation. On the other hand, if these algorithms are coupled with multi modular arithmetic, the bit complexity may be reduced to [[soft O notation. In sorting and searching, the resource that is generally considered is the number of entry comparisons. This is generally a good measure of the time complexity if data are suitably organized.
Кіріс көлеміне байланысты күрделілік
Барлық мүмкін кіріс мәліметтері бойынша алгоритмнің қадамдарын санау мүмкін емес. Күрделілік көбінесе кіріс көлеміне байланысты өседі, сондықтан күрделілік әдетте кіріс n (биттермен) мөлшерінің функциясы ретінде беріледі, демек, күрделілік n функциясы болып табылады. Дегенмен, алгоритмнің күрделілігі бірдей мөлшердегі әртүрлі кіріс мәліметтері үшін айтарлықтай өзгеруі мүмкін. Сондықтан, бірнеше күрделілік функциялары қолданылады. Ең нашар жағдай күрделілігі – n мөлшеріндегі барлық кіріс мәліметтері бойынша күрделіліктің ең жоғарғы мәні, ал орташа жағдай күрделілігі – n мөлшеріндегі барлық кіріс мәліметтері бойынша күрделіліктің орташа мәні (бұл түсінікті, себебі белгілі бір мөлшердегі мүмкін кіріс мәліметтерінің саны шектеулі). Әдетте, егер "күрделілік" термині қосымша нақтыланбаса, ең нашар жағдайдың уақыт күрделілігі қарастырылады.
It is impossible to count the number of steps of an algorithm on all possible inputs. As the complexity generally increases with the size of the input, the complexity is typically expressed as a function of the size n (in bits) of the input, and therefore, the complexity is a function of n. However, the complexity of an algorithm may vary dramatically for different inputs of the same size. Therefore, several complexity functions are commonly used. The worst case complexity is the maximum of the complexity over all inputs of size n, and the average case complexity is the average of the complexity over all inputs of size n (this makes sense, as the number of possible inputs of a given size is finite). Generally, when "complexity" is used without being further specified, this is the worst case time complexity that is considered.
Есептеу үлгілері
Күрделілікті бағалау есептеу моделін таңдауға негізделеді, ол бірлік уақытта орындалатын негізгі амалдарды анықтаудан тұрады. Егер есептеу моделі нақты көрсетілмесе, көбінесе ол көп таспалы Тьюринг машинасы деп есептеледі, себебі кездейсоқ кіру машиналары сияқты көптеген шынайы есептеу модельдері көптеген мәселелер үшін асимптотикалық жағынан эквивалентті болып табылады. Тек өте нақты және қиын мәселелер үшін, мысалы, белгілі бір уақытта бүтін сандарды көбейту сияқты жағдайларда, дәлелдеу үшін есептеу моделінің нақты анықтамасы қажет.
The evaluation of the complexity relies on the choice of a model of computation, which consists in defining the basic operations that are done in a unit of time. When the model of computation is not explicitly specified, it is generally implicitely assumed as being a multitape Turing machine, since several more realistic models of computation, such as random access machines are asymptotically equivalent for most problems. It is only for very specific and difficult problems, such as integer multiplication in time that the explicit definition of the model of computation is required for proofs.
Детерминистік модельдер
Детерминистік есептеу моделі – машинаның кезекті күйлері мен орындалатын операциялардың алдыңғы күйімен толық анықталатын есептеу моделі. Тарихи тұрғыдан алғанда, алғашқы детерминистік модельдер рекурсивті функциялар, лямбда-есептеу және Тьюринг машиналары болды. Нақты компьютерлерге жақын модель ретінде кездейсоқ кіру машиналарының (RAM машиналары деп те аталады) моделі де кеңінен қолданылады. Егер есептеу моделі көрсетілмесе, ол әдетте көп таспалы Тьюринг машинасы деп есептеледі. Көптеген алгоритмдер үшін уақыт күрделілігі көп таспалы Тьюринг машиналарында да, RAM машиналарында да бірдей болады, бірақ осы теңдестікті алу үшін деректерді жадта сақтау тәсіліне назар аудару қажет болуы мүмкін.
A deterministic model of computation is a model of computation such that the successive states of the machine and the operations to be performed are completely determined by the preceding state. Historically, the first deterministic models were recursive functions, lambda calculus, and Turing machines. The model of random access machines (also called RAM machines) is also widely used, as a closer counterpart to real computers. When the model of computation is not specified, it is generally assumed to be a multitape Turing machine. For most algorithms, the time complexity is the same on multitape Turing machines as on RAM machines, although some care may be needed in how data is stored in memory to get this equivalence.
Детерминистік емес есептеу
Детерминистік емес есептеу моделінде, мысалы, детерминистік емес Тьюринг машиналарында, есептеудің кейбір қадамдарында таңдаулар жасалуы мүмкін. Күрделілік теориясында барлық мүмкін таңдаулар бір мезгілде қарастырылады, ал детерминистік емес уақыт күрделігі – ең жақсы таңдау әрқашан жасалған кезде қажетті уақыт. Басқаша айтқанда, есептеу қажет болған жағдайда бірдей процессорлардың санымен бір мезгілде жүзеге асырылады деп есептеледі, ал детерминистік емес есептеу уақыты – есептеуді бірінші аяқтаған процессордың жұмсаған уақыты. Бұл параллелизм кванттық есептеулерде, белгілі бір кванттық алгоритмдерді іске асыру кезінде, суперпозицияланған байланысқан күйлер арқылы іске асырылуы мүмкін, мысалы, Шордың әлі де кішкентай бүтін сандарды жіктеуі (2018 жылғы мәлімет бойынша: 21 = 3 × 7). Мұндай есептеу моделі әлі де нақты болмаса да, оның теориялық маңызы зор, көбінесе P = NP мәселесімен байланысты, ол «полиномиалдық уақыт» және «детерминистік емес полиномиалдық уақыт» ең төменгі жоғарғы шек ретінде қарастырылатын күрделілік сыныптарының теңдігіне күмәндік тудырады. Детерминистік компьютерде NP алгоритмін модельдеу әдетте «экспоненциалдық уақыт» алады. Егер мәселені детерминистік емес машинада полиномиалдық уақытта шешуге болады, онда ол NP күрделілік класына жатады. Мәселе NP-толық деп есептеледі, егер ол NP класына жататын болса және басқа NP мәселелерінен қиын болмаса. Көптеген комбинаторлық мәселелер, мысалы, рюкзак мәселесі, саяхатшы мәселесі және Бульдік қанағаттандыру мәселесі NP-толық. Осы мәселелердің барлығы үшін ең жақсы белгілі алгоритм экспоненциалдық күрделілікке ие. Егер осы мәселелердің кез келгенін детерминистік машинада полиномиалдық уақытта шешуге мүмкіндік болса, онда барлық NP мәселелерін де полиномиалдық уақытта шешуге болады, яғни P = NP болады. 2017 жылдан бері P ≠ NP деген болжам кеңінен таралған, бұл NP мәселелерінің ең нашар жағдайларын шешудің қиындығын көрсетеді, яғни кірістің қызықты ұзындығы үшін ондаған жылдардан астам уақыт қажет болуы мүмкін.
In a non deterministic model of computation, such as non deterministic Turing machines, some choices may be done at some steps of the computation. In complexity theory, one considers all possible choices simultaneously, and the non deterministic time complexity is the time needed, when the best choices are always done. In other words, one considers that the computation is done simultaneously on as many (identical) processors as needed, and the non deterministic computation time is the time spent by the first processor that finishes the computation. This parallelism is partly amenable to quantum computing via superposed entangled states in running specific quantum algorithms, like e. g. Shor's factorization of yet only small integers (as of 2018: 21 = 3 × 7). Even when such a computation model is not realistic yet, it has theoretical importance, mostly related to the P = NP problem, which questions the identity of the complexity classes formed by taking "polynomial time" and "non deterministic polynomial time" as least upper bounds. Simulating an NP algorithm on a deterministic computer usually takes "exponential time". A problem is in the complexity class NP, if it may be solved in polynomial time on a non deterministic machine. A problem is NP complete if, roughly speaking, it is in NP and is not easier than any other NP problem. Many combinatorial problems, such as the Knapsack problem, the travelling salesman problem, and the Boolean satisfiability problem are NP complete. For all these problems, the best known algorithm has exponential complexity. If any one of these problems could be solved in polynomial time on a deterministic machine, then all NP problems could also be solved in polynomial time, and one would have P = NP. as of 2017 it is generally conjectured that P ≠ NP, with the practical implication that the worst cases of NP problems are intrinsically difficult to solve, i. e., take longer than any reasonable time span (decades!) for interesting lengths of input.
Параллель және үлестірілген есептеулер
Параллель және үлестірілген есептеулер бірнеше процессорда есептеуді бөлуден тұрады, олар бір уақытта жұмыс істейді. Модельдер арасындағы айырмашылық негізінен процессорлар арасында ақпаратты жіберу тәсілінде. Әдетте, параллель есептеулерде процессорлар арасындағы деректерді беру өте жылдам, ал үлестірілген есептеулерде деректер желі арқылы жіберіледі, сондықтан ол әлдеқайда баяу. N процессорда есептеуге қажетті уақыт, ең болмағанда, бір процессорға қажетті уақытты N-ге бөлгенге тең болады. Бірақ, бұл теориялық ең жақсы көрсеткіштің өзіне жете алмайсыз, себебі кейбір кішірек есептерді параллельдеу мүмкін емес, ал кейбір процессорлар басқа процессордан нәтиже күтуі мүмкін. Сондықтан, басты қиындық – есептеу уақытын процессорлар санына көбейту нәтижесі, бір процессордағы осы есепке қажетті уақытқа мүмкіндігінше жақын болатын алгоритмдерді жасау.
Parallel and distributed computing consist of splitting computation on several processors, which work simultaneously. The difference between the different model lies mainly in the way of transmitting information between processors. Typically, in parallel computing the data transmission between processors is very fast, while, in distributed computing, the data transmission is done through a network and is therefore much slower. The time needed for a computation on N processors is at least the quotient by N of the time needed by a single processor. In fact this theoretically optimal bound can never be reached, because some subtasks cannot be parallelized, and some processors may have to wait a result from another processor. The main complexity problem is thus to design algorithms such that the product of the computation time by the number of processors is as close as possible to the time needed for the same computation on a single processor.
Кванттық есептеу
Кванттық компьютер – кванттық механикаға негізделген есептеу моделіне ие компьютер. Черч-Тюринг тезисі кванттық компьютерлерге де қатысты; яғни, кванттық компьютер шеше алатын кез келген мәселені Тьюринг машинасы да шеше алады. Дегенмен, кейбір мәселелер теориялық тұрғыдан классикалық компьютерге қарағанда кванттық компьютер арқылы әлдеқайда төмен уақыт күрделілігімен шешілуі мүмкін. Қазіргі таңда бұл тек теориялық мүмкіндік, себебі ешкім тиімді кванттық компьютерді қалай құруға болатынын білмейді. Кванттық күрделілік теориясы кванттық компьютерлерді пайдаланып шешілетін мәселелердің күрделілік кластарын зерттеу үшін жасалған. Ол кванттық компьютерлердің шабуылдарына қарсы тұратын криптографиялық протоколдарды құрудан тұратын кванттық криптографиядан кейінгі криптографияда қолданылады.
A quantum computer is a computer whose model of computation is based on quantum mechanics. The Church–Turing thesis applies to quantum computers; that is, every problem that can be solved by a quantum computer can also be solved by a Turing machine. However, some problems may theoretically be solved with a much lower time complexity using a quantum computer rather than a classical computer. This is, for the moment, purely theoretical, as no one knows how to build an efficient quantum computer. Quantum complexity theory has been developed to study the complexity classes of problems solved using quantum computers. It is used in post quantum cryptography, which consists of designing cryptographic protocols that are resistant to attacks by quantum computers.
Мәселе күрделілігі (төменгі шектер)
Мәселенің күрделілігі – мәселені шеше алатын алгоритмдердің күрделілігінің инфимумы, соның ішінде белгісіз алгоритмдер де бар. Осылайша, мәселенің күрделілігі, мәселені шешетін кез келген алгоритмнің күрделілігінен жоғары болмайды. Содан шығатыны, алгоритмнің үлкен O нотациясымен көрсетілген әрбір күрделілігі, сәйкес мәселенің күрделілігінің жоғарғы шегі болып табылады. Екінші жағынан, мәселенің күрделілігі үшін тривиальды емес төменгі шектерді алу әдетте қиын, және мұндай төменгі шектерді алуға арналған әдістер де аз. Көптеген мәселелерді шешу үшін барлық кіріс деректерін оқу қажет, бұл әдетте деректердің көлеміне пропорционалды уақытты қажет етеді. Осылайша, мұндай мәселелердің күрделілігі кем дегенде сызықтық, яғни үлкен омега нотациясын қолдану арқылы, күрделілігі болады.
The complexity of a problem is the infimum of the complexities of the algorithms that may solve the problem, including unknown algorithms. Thus the complexity of a problem is not greater than the complexity of any algorithm that solves the problems. It follows that every complexity of an algorithm, that is expressed with big O notation, is also an upper bound on the complexity of the corresponding problem. On the other hand, it is generally hard to obtain nontrivial lower bounds for problem complexity, and there are few methods for obtaining such lower bounds. For solving most problems, it is required to read all input data, which, normally, needs a time proportional to the size of the data. Thus, such problems have a complexity that is at least linear, that is, using big omega notation, a complexity
Кейбір мәселелердің шешімі, әдетте компьютерлік алгебра және есептеу алгебралық геометриясында, өте үлкен болуы мүмкін. Мұндай жағдайда, күрделілік ең төменгі шегі шығыстың максималды көлемімен шектеледі, өйткені шығысты жазу қажет. Мысалы, n анықталмаған n дәрежелі d көптамалы теңдеулер жүйесі, егер шешімдер саны шекті болса, дейін кешенді шешімдерге ие болуы мүмкін (бұл Безу теоремасы). Бұл шешімдерді жазу керек болғандықтан, бұл мәселенің күрделілігі болады. Бұл мәселенің күрделілігі алгоритмі белгілі, сондықтан оны асимптотикалық квази-оптималды деп санауға болады. Сорттау алгоритміне қажетті салыстырулар саны үшін сызықтық емес төменгі шек белгілі. Осылайша, ең жақсы сорттау алгоритмдері оңтайлы, өйткені олардың күрделілігі болады. Бұл төменгі шек n нысанды реттеудің n! тәсілі бар деген фактіден туындайды. Әр салыстыру n! реттіліктер жиынтығын екіге бөледі, сондықтан барлық реттіліктерді ажырату үшін қажетті N салыстырулар саны тексеруі керек, бұл Стирлинг формуласы бойынша анықталады. Күрделіліктің төменгі шектерін алудың стандартты әдісі бір мәселені екінші мәселеге келтіруден тұрады. Нақтырақ айтқанда, егер n өлшемдегі A мәселесін B мәселесінің f(n) өлшемдегі қосалқы мәселесіне кодтауға болады деп есептесек, және A мәселесінің күрделілігі болса, онда жалпылықты жоғалтпай, f функциясы n-мен өседі және кері функциясы h болады деп есептеуге болады. Содан кейін B мәселесінің күрделілігі болады. Бұл P ≠ NP (шешілмеген болжам) болса, әрбір NP-толық мәселенің күрделілігі әрбір оң бүтін сан k үшін екенін дәлелдеу үшін қолданылатын әдіс.
The solution of some problems, typically in computer algebra and computational algebraic geometry, may be very large. In such a case, the complexity is lower bounded by the maximal size of the output, since the output must be written. For example, a system of n polynomial equations of degree d in n indeterminates may have up to complex solutions, if the number of solutions is finite (this is Bézout's theorem). As these solutions must be written down, the complexity of this problem is For this problem, an algorithm of complexity is known, which may thus be considered as asymptotically quasi optimal. A nonlinear lower bound of is known for the number of comparisons needed for a sorting algorithm. Thus the best sorting algorithms are optimal, as their complexity is This lower bound results from the fact that there are n! ways of ordering n objects. As each comparison splits in two parts this set of n! orders, the number of N of comparisons that are needed for distinguishing all orders must verify which implies by Stirling's formula. A standard method for getting lower bounds of complexity consists of reducing a problem to another problem. More precisely, suppose that one may encode a problem A of size n into a subproblem of size f(n) of a problem B, and that the complexity of A is Without loss of generality, one may suppose that the function f increases with n and has an inverse function h. Then the complexity of the problem B is This is the method that is used to prove that, if P ≠ NP (an unsolved conjecture), the complexity of every NP complete problem is for every positive integer k.
Алгоритмдерді жобалауда қолдану
Алгоритмнің күрделілігін бағалау – алгоритмді жобалаудың маңызды бөлігі, себебі ол күтілетін өнімділік туралы пайдалы ақпарат береді. Алгоритмдердің күрделілігін бағалау Мур заңының нәтижесінде маңыздылығы азаяды деген жалпы қате түсінік бар, Мур заңы қазіргі заманғы компьютерлердің қуатының экспоненциалды өсуін болжайды. Бұл дұрыс емес, өйткені қуаттың артуы үлкен көлемді деректермен (үлкен деректер) жұмыс істеуге мүмкіндік береді. Мысалы, кітаптың библиографиясы сияқты бірнеше жүз жазбаны әліппелік тәртіппен сұрыптау қажет болғанда, кез келген алгоритм бір секундтан кем уақытта жақсы жұмыс істеуі керек. Алайда, миллион жазбадан тұратын тізім үшін (мысалы, ірі қаланың телефон нөмірлері), салыстыруды қажет ететін қарапайым алгоритмдер триллиондаған салыстырулар жасауы керек, бұл секундына 10 миллион салыстыру жылдамдығымен шамамен үш сағатқа созылады. Ал жылдам сұрыптау (quicksort) және біріктіру сұрыптау (merge sort) үшін салыстыру саны тек (бұрынғысы үшін орташа жағдайда, соңғысы үшін ең нашар жағдайда) қана қажет. n = 1,000,000 болғанда, бұл шамамен 30,000,000 салыстыруға тең, ал секундына 10 миллион салыстыру жылдамдығымен бұл 3 секундты алады. Осылайша, күрделілікті бағалау кез келген іске асырудан бұрын көптеген тиімсіз алгоритмдерді жоюға мүмкіндік береді. Бұл күрделі алгоритмдерді барлық нұсқаларын сынамай-ақ жақсарту үшін де қолданылуы мүмкін. Күрделі алгоритмнің ең қымбат қадамдарын анықтау арқылы күрделілікті зерттеу, осы қадамдарға күш-жігерді жұмсауға және іске асырудың тиімділігін арттыруға мүмкіндік береді.
Evaluating the complexity of an algorithm is an important part of algorithm design, as this gives useful information on the performance that may be expected. It is a common misconception that the evaluation of the complexity of algorithms will become less important as a result of Moore's law, which posits the exponential growth of the power of modern computers. This is wrong because this power increase allows working with large input data (big data). For example, when one wants to sort alphabetically a list of a few hundreds of entries, such as the bibliography of a book, any algorithm should work well in less than a second. On the other hand, for a list of a million of entries (the phone numbers of a large town, for example), the elementary algorithms that require comparisons would have to do a trillion of comparisons, which would need around three hours at the speed of 10 million of comparisons per second. On the other hand, the quicksort and merge sort require only comparisons (as average case complexity for the former, as worst case complexity for the latter). For 1=n = 1,000,000, this gives approximately 30,000,000 comparisons, which would only take 3 seconds at 10 million comparisons per second. Thus the evaluation of the complexity may allow eliminating many inefficient algorithms before any implementation. This may also be used for tuning complex algorithms without testing all variants. By determining the most costly steps of a complex algorithm, the study of complexity allows also focusing on these steps the effort for improving the efficiency of an implementation.