Үлкен-Ω (Үлкен-Омега) белгісі

Кейде біз алгоритм жоғарғы шекараны көрсетпестен кем дегенде белгілі бір уақытты алады деп айтқымыз келеді. Біз үлкен Ω белгісін қолданамыз; бұл грек әрпі "омега".

Егер жұмыс уақыты $\Omega(f(n))$\Omega, left parenthesis, f, left parenthesis, n, right parenthesis, right parenthesis болса, онда жеткілікті үлкен $n$n үшін жұмыс уақыты $k \cdot f(n)$k, dot, f, left parenthesis, n, right parenthesis - дан кем емес. Мұнда $\Omega(f(n))$\Omega, left parenthesis, f, left parenthesis, n, right parenthesis, right parenthesis - ға тең жұмыс уақытын көрсету керек:

Біз орындау уақыты "Үлкен-Ω $f (n)$f, left parenthesis, n, right parenthesis" деп айтамыз. Біз үлкен-Ω белгілеуін асимптотикалық төменгі шекаралар үшін қолданамыз, өйткені ол жеткілікті үлкен кіріс өлшемдері үшін төменнен жұмыс уақытының өсуін шектейді.

Мысалға $\Theta(f(n))$\Theta, left parenthesis, f, left parenthesis, n, right parenthesis, right parenthesis автоматты түрде осыны білдіреді $O(f(n))$O, left parenthesis, f, left parenthesis, n, right parenthesis, right parenthesis, бұл да автоматты түрде осыны білдіреді $\Omega(f(n))$\Omega, left parenthesis, f, left parenthesis, n, right parenthesis, right parenthesis. Сонымен, екілік іздеудің ең нашар уақыты $\Omega(\log_2 n)$\Omega, left parenthesis, log, start base, 2, end base, n, right parenthesis. деп айта аламыз

Үлкен Ω белгісін қолдана отырып, біз дұрыс, бірақ дәл емес мәлімдемелер жасай аламыз. Мысалы, егер сіздің қалтаңызда миллион доллар болса, сіз шынымен айта аласыз: "менің қалтаңызда ақша бар, және бұл кем дегенде 10 доллар."Бұл дұрыс, бірақ, әрине, дәл емес. Сол сияқты, біз екілік іздеудің ең нашар уақыты деп дұрыс айта аламыз, бірақ дәл емес $\Omega(1)$\Omega, left parenthesis, 1, right parenthesis, себебі біз бұл үшін кем дегенде тұрақты уақыт қажет екенін білеміз.

Әрине, әдетте Алгоритмдер туралы сөйлескенде, біз олардың орындалу уақытын мүмкіндігінше дәл сипаттауға тырысамыз. Үлкендерді жақсы түсінуге көмектесу үшін біз мұнда дұрыс емес тұжырымдардың мысалдарын келтіреміз-$\Omega$\Omega, үлкен-$O$O, және үлкен-$\Theta$\Theta.

Бұл мазмұн ынтымақтастықтың нәтижесі Дартмут компьютерлік ғылымы профессорлар [Томас Кормен](http://www.cs.dartmouth.edu / ~thc/) және [Дэвин Бэлком](http://www.cs.dartmouth.edu / ~devin/), сонымен қатар Хан академиясының компьютерлік оқу бағдарламасы бойынша тобы. Мазмұн лицензияланған CC-BY-NC-SA.