[Powered by Google Translate] איר ווע מיסטאָמע געהערט מענטשן רעדן וועגן אַ פעסט אָדער עפעקטיוו אַלגערידאַם פֿאַר עקסאַקיוטינג דיין באַזונדער אַרבעט, אָבער וואָס פּונקט טוט עס מיינען פֿאַר אַ אַלגערידאַם צו זייַן פעסט אָדער עפעקטיוו? נו, עס ס ניט גערעדט וועגן אַ מעאַסורעמענט אין פאַקטיש צייַט, ווי סעקונדעס אָדער מינוט. דאס איז ווייַל קאָמפּיוטער ייַזנוואַרג און ווייכווארג בייַטן דראַסטיקלי. מייַן פּראָגראַם זאל לויפן סלאָוער ווי דייַן, ווייַל איך בין פליסנדיק עס אויף אַ עלטערע קאָמפּיוטער, אָדער ווייַל איך פּאַסירן צו זייַן פּלייינג אַן אָנליין ווידעא שפּיל אין דער זעלביקער צייַט, וואָס איז כאָגינג אַלע מיין זכּרון, אָדער איך זאל זייַן פליסנדיק מיין פּראָגראַם דורך פאַרשידענע ווייכווארג וואָס קאַמיוניקייץ מיט די מאַשין דיפערענטלי בייַ אַ נידעריק מדרגה. עס ס ווי קאַמפּערינג apples און אָראַנדזשאַז. נאָר ווייַל מיין סלאָוער קאָמפּיוטער נעמט מער ווי דייַן צו געבן צוריק אַן ענטפֿערן טוט נישט מיינען איר האָבן די מער עפעקטיוו אַלגערידאַם. 

אַזוי, זינט מיר קענען ניט גלייַך פאַרגלייַכן די רונטימעס פון מגילה אין סעקונדעס אָדער מינוט, ווי טאָן מיר פאַרגלייַכן 2 פאַרשידענע אַלגערידאַמז ראַגאַרדלאַס פון זייער ייַזנוואַרג אָדער ווייכווארג סוויווע? צו שאַפֿן אַ מער מונדיר וועג פון מעסטן אַלגאָריטהמיק עפעקטיווקייַט, קאָמפּיוטער סיינטיס און מאַטאַמאַטישאַנז האָבן דיווייזד קאַנסעפּס פֿאַר מעסטן די אַסימפּטאָטיק קאַמפּלעקסיטי פון אַ פּראָגראַם און אַ נאָוטיישאַן גערופן 'גרויס אָהנאָטאַטיאָן' פֿאַר דיסקרייבינג דעם. די פאָרמאַל דעפֿיניציע איז אַז אַ פֿונקציע F (X) לויפט אויף די סדר פון ג (X) אויב עס יגזיסץ עטלעכע (X) ווערט, X ₀ און עטלעכע קעסיידערדיק, C, פֿאַר וואָס F (X) איז ווייניקער ווי אָדער גלייַך צו אַז קעסיידערדיק מאל ג (X) פֿאַר אַלע X גרעסער ווי X ₀. 

אבער טאָן נישט זייַן דערשראָקן אַוועק דורך די פאָרמאַל דעפֿיניציע. וואָס טוט דאָס פאקטיש מיינען אין ווייניקער טעאָרעטיש תּנאָים? נו, עס ס בייסיקלי אַ וועג פון אַנאַלייזינג ווי שנעל אַ פּראָגראַם 'ס רונטימע וואקסט אַסימפּטאָטיקאַללי. וואָס איז, ווי די גרייס פון דיין ינפּוץ ינקריסיז צו ינפיניטי, זאָגן, איר ניטאָ סאָרטינג אַ מענגע פון ​​גרייס 1000 קאַמפּערד צו אַ מענגע פון ​​גרייס 10. ווי טוט די רונטימע פון ​​דיין פּראָגראַם וואַקסן? פֿאַר בייַשפּיל, ימאַדזשאַן קאַונטינג די נומער פון אותיות אין אַ שטריקל די סימפּלאַסט וועג  דורך גיין דורך די גאנצע שטריקל בריוו-דורך-בריוו און אַדינג 1 צו אַ קאָונטער פֿאַר יעדער כאַראַקטער. דאס אַלגערידאַם איז געזאגט צו לויפן אין לינעאַר צייַט מיט רעספּעקט צו די נומער פון אותיות, 'N' אין די שטריקל. אין קורץ, עס לויפט אין אָ (N). פארוואס איז דאָס? נו, ניצן דעם צוגאַנג, די צייַט פארלאנגט צו דורך די גאנצע שטריקל איז פּראַפּאָרשאַנאַל צו די נומער פון אותיות. קאַונטינג די נומער פון אותיות אין אַ 20-כאַראַקטער שטריקל איז געגאנגען צו נעמען צוויי מאָל ווי לאַנג ווי עס נעמט צו ציילן די אותיות אין אַ 10-כאַראַקטער שטריקל, ווייַל איר האָבן צו קוקן אין אַלע די אותיות און יעדער כאַראַקטער נעמט די זעלבע סומע פון ​​צייַט צו קוקן בייַ. ווי איר פאַרגרעסערן די נומער פון אותיות, די רונטימע וועט פאַרגרעסערן ליניערלי מיט די אַרייַנשרייַב לענג. 

איצט, ימאַדזשאַן אויב איר באַשליסן אַז לינעאַר צייַט, אָ (N), נאָר איז געווען ניט שנעל גענוג פֿאַר איר? אפֿשר איר ניטאָ סטאָרינג ריזיק סטרינגס, און איר קענען נישט פאַרגינענ די עקסטרע מאָל עס וואָלט נעמען צו דורך אַלע פון ​​זייער אותיות קאַונטינג איינער-דורך-איינער. אַזוי, איר באַשליסן צו פּרובירן עפּעס אַנדערש. וואָס אויב איר וואָלט פּאַסירן צו שוין קראָם די נומער פון אותיות אין דעם שטריקל, זאָגן, אין אַ בייַטעוודיק גערופן 'לען,' פרי אויף אין די פּראָגראַם, איידער איר אַפֿילו סטאָרד די זייער ערשטער כאַראַקטער אין דיין שטריקל? דערנאך, אַלע איר 'ד האָבן צו טאָן איצט צו געפֿינען אויס די שטריקל לענג, איז טשעק וואָס די ווערט פון די בייַטעוודיק איז. איר וואָלט ניט האָבן צו קוקן בייַ די שטריקל זיך בייַ אַלע, און אַקסעסינג די ווערט פון אַ בייַטעוודיק ווי לען איז געהאלטן אַ אַסימפּטאָטיקאַללי קעסיידערדיק צייַט אָפּעראַציע, אָדער אָ (1). פארוואס איז דאָס? נו, געדענקען וואָס אַסימפּטאָטיק קאַמפּלעקסיטי מיטל. ווי טוט די רונטימע טוישן ווי די גרייס פון דיין ינפּוץ וואקסט? 

זאָגן איר זענען טריינג צו באַקומען די נומער פון אותיות אין אַ ביגער שטריקל. נו, עס וואָלט נישט ענין ווי גרויס איר מאַכן דעם שטריקל, אַפֿילו אַ מיליאָן אותיות לאַנג, אַלע איר 'ד האָבן צו טאָן צו געפֿינען די שטריקל ס לענג מיט דעם צוגאַנג, איז צו לייענען אויס די ווערט פון די בייַטעוודיק לען, וואָס איר שוין געמאכט. די אַרייַנשרייַב לענג, וואָס איז, די לענג פון די שטריקל איר ניטאָ טריינג צו געפֿינען, טוט ניט ווירקן אין אַלע ווי שנעל דיין פּראָגראַם לויפט. דעם טייל פון אייער פּראָגראַם וואָלט לויפן גלייַך פעסט אויף אַ איין-כאַראַקטער שטריקל און אַ טויזנט-כאַראַקטער שטריקל, און אַז ס וואָס דעם פּראָגראַם וואָלט זייַן ריפערד צו ווי פליסנדיק אין קעסיידערדיק צייַט מיט רעספּעקט צו די אַרייַנשרייַב גרייס. 

פון קורס, דאָרט ס אַ שטערונג. איר פאַרברענגען עקסטרע זכּרון פּלאַץ אויף דיין קאָמפּיוטער סטאָרינג די בייַטעוודיק און די עקסטרע צייַט עס נעמט איר צו טאָן די פאַקטיש סטאָרידזש פון די בייַטעוודיק, אָבער די פונט נאָך שטייט, געפונען אויס ווי לאַנג דיין שטריקל איז געווען טוט ניט אָפענגען אויף די לענג פון די שטריקל בייַ אַלע. אַזוי, עס לויפט אין אָ (1) אָדער קעסיידערדיק צייַט. דאס זיכער טוט ניט האָבן צו מיינען אַז דיין קאָד לויפט אין 1 שריט, אָבער קיין ענין ווי פילע טריט עס איז, אויב עס טוט נישט טוישן מיט די גרייס פון דעם ינפּוץ, עס ס נאָך אַסימפּטאָטיקאַללי קעסיידערדיק וואָס מיר פאָרשטעלן ווי אָ (1). 

ווי איר קענען מיסטאָמע טרעפן, עס זענען פילע פאַרשידענע גרויס אָ רונטימעס צו מאָס אַלגערידאַמז מיט. אָ (N) ² אַלגערידאַמז זענען אַסימפּטאָטיקאַללי סלאָוער ווי אָ (N) אַלגערידאַמז. וואָס איז, ווי די נומער פון עלעמענטן (N) וואקסט, יווענטשאַוואַלי אָ (N) ² אַלגערידאַמז וועט נעמען מער צייַט ווי אָ (N) אַלגערידאַמז צו לויפן. דאס טוט נישט מיינען אָ (N) אַלגערידאַמז שטענדיק לויפן פאַסטער ווי אָ (N) ² אַלגערידאַמז, אַפֿילו אין דער זעלביקער סוויווע, אויף דער זעלביקער ייַזנוואַרג. אפֿשר פֿאַר קליין אַרייַנשרייַב סיזעס,  דער אָ (N) ² אַלגערידאַם זאל פאקטיש אַרבעט פאַסטער, אָבער, יווענטשאַוואַלי, ווי די אַרייַנשרייַב גרייס ינקריסיז צו ינפיניטי, די אָ (N) ² אַלגערידאַם ס רונטימע וועט יווענטשאַוואַלי אַקליפּס די רונטימע פון ​​די אָ (N) אַלגערידאַם. פּונקט ווי קיין קוואַדראַטיק מאַטאַמאַטיקאַל פֿונקציע  וועט יווענטשאַוואַלי יבעריאָגן קיין לינעאַר פונקציאָנירן, קיין ענין ווי פיל פון אַ קאָפּ אָנהייב די לינעאַר פונקציאָנירן סטאַרץ אַוועק מיט. אויב איר ניטאָ ארבעטן מיט גרויס אַמאַונץ פון דאַטן, אַלגערידאַמז וואָס לויפן אין אָ (N) ² צייַט קענען טאַקע סוף אַרויף סלאָוינג אַראָפּ דיין פּראָגראַם, אָבער פֿאַר קליין אַרייַנשרייַב סיזעס, איר מיסטאָמע וועט נישט אַפֿילו באַמערקן. 

אן אנדער אַסימפּטאָטיק קאַמפּלעקסיטי איז, לאַגערידמיק צייַט, אָ (קלאָץ N). אַ בייַשפּיל פון אַ אַלגערידאַם וואָס לויפט דעם געשווינד איז דער קלאַסיש ביינערי זוכן אַלגערידאַם, פֿאַר געפונען אַן עלעמענט אין אַ שוין-אויסגעשטעלט רשימה פון עלעמענטן. 

אויב איר טאָן ניט וויסן וואָס ביינערי זוכן טוט, איך וועט דערקלערן עס פֿאַר איר טאַקע געשווינד. זאל ס זאָגן איר ניטאָ קוקן פֿאַר די נומער 3 אין דעם מענגע פון ​​ינטאַדזשערז. עס קוקט אין די מיטל עלעמענט פון דער מענגע און פרעגט, "איז דער עלעמענט איך וועלן גרעסער ווי, גלייַך צו, אָדער ווייניקער ווי דעם?" אויב עס ס גלייַך, דעמאָלט גרויס. איר געפונען דעם עלעמענט, און איר ניטאָ געטאן. אויב עס ס גרעסער, דעמאָלט איר וויסן דעם עלעמענט האט צו זייַן אין די רעכט זייַט פון די מענגע, און איר קענען נאָר קוק אין אַז אין די צוקונפֿט, און אויב עס ס קלענערער, ​​דעמאָלט איר וויסן עס האט צו זייַן אין די לינקס זייַט. דעם פּראָצעס איז דעמאָלט ריפּיטיד מיט דער קלענערער-גרייס מענגע ביז די ריכטיק עלעמענט איז געפונען. 

דאס שטאַרק אַלגערידאַם קאַץ די מענגע גרייס אין העלפט מיט יעדער אָפּעראַציע. אַזוי, צו געפֿינען אַן עלעמענט אין אַ אויסגעשטעלט מענגע פון ​​נומער 8, בייַ רובֿ (קלאָץ ₂ 8), אָדער 3 פון די אַפּעריישאַנז, קאָנטראָלירונג די מיטל עלעמענט, דעמאָלט קאַטינג די מענגע אין האַלב וועט זייַן פארלאנגט, וועראַז אַ מענגע פון ​​גרייס 16 נעמט (קלאָץ ₂ 16), אָדער 4 אַפּעריישאַנז. אַז ס בלויז 1 מער אָפּעראַציע פֿאַר אַ דאַבאַלד-גרייס מענגע. דאַבלינג די גרייס פון דעם מענגע ינקריסיז די רונטימע דורך בלויז 1 פּייַדע פון ​​דעם קאָד. ווידער, קאָנטראָלירונג די מיטל עלעמענט פון דער רשימה, דעמאָלט ספּליטינג. אַזוי, עס ס 'האט צו אַרבעטן אין לאַגערידמיק צייַט, אָ (קלאָץ N). אבער וואַרטן, איר זאָגן, טוט ניט דעם אָפענגען אויף ווו אין די רשימה די עלעמענט איר ניטאָ קוקן פֿאַר איז? וואָס אויב דער ערשטער עלעמענט איר קוק בייַ כאַפּאַנז צו זייַן די רעכט איינער? דעמאָלט, עס נאָר נעמט 1 אָפּעראַציע, קיין ענין ווי גרויס די רשימה איז. 

נו, אַז ס וואָס קאָמפּיוטער סיינטיס האָבן מער תּנאָים פֿאַר אַסימפּטאָטיק קאַמפּלעקסיטי וואָס פאַרטראַכטנ דער בעסטער-פאַל און ערגסט-פאַל פּערפאָרמאַנסיז פון אַ אַלגערידאַם. מער רעכט, דער אויבערשטער און נידעריקער גווול אויף די רונטימע. אין דער בעסטער פאַל פֿאַר ביינערי זוכן, אונדזער עלעמענט איז רעכט דאָרט אין דער מיטן, און איר באַקומען עס אין קעסיידערדיק צייַט, קיין ענין ווי גרויס די מנוחה פון די מענגע איז. דער סימבאָל געניצט פֿאַר דעם איז Ω. אַזוי, דעם אַלגערידאַם איז געזאגט צו לויפן אין Ω (1). אין דער בעסטער פאַל, עס געפינט די עלעמענט געשווינד, קיין ענין ווי גרויס די מענגע איז, אָבער אין די ערגסט פאַל, עס האט צו דורכפירן (קלאָץ N) שפּאַלטן טשעקס פון די מענגע צו געפֿינען די רעכט עלעמענט. ערגסט-פאַל אויבערשטער גווול זענען ריפערד צו מיט די גרויס "אָ" אַז איר שוין וויסן. אַזוי, עס ס אָ (קלאָץ N), אָבער Ω (1). 

א לינעאַר זוכן, דורך קאַנטראַסט, אין וואָס איר גיין דורך יעדער עלעמענט פון דער מענגע צו געפֿינען די איין איר ווילן, איז בייַ בעסטער Ω (1). ווידער, דער ערשטער עלעמענט איר ווילן. אַזוי, עס טוט נישט ענין ווי גרויס די מענגע איז. אין די ערגסט פאַל, עס ס די לעצטע עלעמענט אין דער מענגע. אַזוי, איר האָבן צו גיין דורך אַלע N יסודות אין די מענגע צו געפֿינען עס, ווי אויב איר זענען קוקן פֿאַר אַ 3. אַזוי, עס לויפט אין אָ (N) צייַט ווייַל עס ס פּראַפּאָרשאַנאַל צו די נומער פון עלעמענטן אין דער מענגע. 

איינער מער סימבאָל געניצט איז Θ. דאס קען זייַן געניצט צו באַשרייַבן אַלגערידאַמז ווו דער בעסטער און ערגסט פאלן זענען די זעלבע. דאס איז דער פאַל אין די שטריקל-לענג אַלגערידאַמז מיר גערעדט וועגן פריער. וואָס איז, אויב מיר קראָם עס אין אַ בייַטעוודיק איידער מיר קראָם די שטריקל און צוטריט עס שפּעטער אין קעסיידערדיק צייַט. ניט קיין ענין וואָס נומער מיר רע סטאָרינג אין אַז בייַטעוודיק, מיר וועט האָבן צו קוקן בייַ אים. דער בעסטער פאַל איז, מיר קוקן אין עס און געפֿינען די לענג פון די שטריקל. אַזוי Ω (1) אָדער בעסטער-פאַל קעסיידערדיק צייַט. די ערגסט פאַל איז, מיר קוקן אין עס און געפֿינען די לענג פון די שטריקל. אַזוי, אָ (1) אָדער קעסיידערדיק צייַט אין ערגסט פאַל. אַזוי, זינט דער בעסטער פאַל און ערגסט פאלן זענען די זעלבע, דעם קענען זייַן האט געזאגט צו לויפן אין Θ (1) מאָל. 

אין קיצער, מיר האָבן גוט וועגן צו סיבה וועגן קאָודז עפעקטיווקייַט אָן געוואוסט עפּעס וועגן די פאַקטיש-וועלט צייַט זיי נעמען צו לויפן, וואָס איז אַפעקטאַד דורך גורל פון אַרויס סיבות, אַרייַנגערעכנט דיפערינג ייַזנוואַרג, סאָפטווער, אָדער די ספּיסיפיקס פון דיין קאָד. אויך, עס אַלאַוז אונדז צו סיבה געזונט וועגן וואָס וועט פּאַסירן ווען די גרייס פון דעם ינפּוץ ינקריסיז. 

אויב איר ניטאָ פליסנדיק אין אָ (N) ² אַלגערידאַם, אָדער ערגער, אַ אָ (2 ⁿ) אַלגערידאַם, איינער פון די פאַסטאַסט גראָוינג טייפּס, איר וועט טאַקע אָנהייבן צו באַמערקן די סלאָודאַון ווען איר אָנהייבן ארבעטן מיט גרעסערע אַמאַונץ פון דאַטן. 

אַז ס אַסימפּטאָטיק קאַמפּלעקסיטי. דאַנק.