תורת החישוביות/סיבוכיות קולמוגורוב: הבדלים בין גרסאות בדף
תוכן שנמחק תוכן שנוסף
שורה 137:
}}
==יישום: חסמים תחתונים לסיבוכיות אלגוריתמים==
===שימוש להוכחת חסם תחתון על סיבוכיות מציאת פלינדרום===
שורה 208:
[[מבני נתונים ואלגוריתמים - מחברת קורס/אלגוריתמים/החסם התחתון על מיון מבוסס-השוואות|חסם תחתון על מיון מבוסס השוואות]]. הרעיון הוא שמיון יעיל מדי היה מוצא דרך לדחוס פרמוטציות מעבר למה שאפשרי קומבינטורית.
==יישום: אורך רצפים בסדרות בינאריות רנדומיות==
נניח סדרה בינרית
<math>x</math> שאורכה הוא
<math>n =|x|</math>.
{{טענה|תוכן=
אם סדרה איננה דחיסה ביותר מ-<math>p</math> קבוע כלשהו, אז
}}
==כלל השרשרת לסיבוכיות==
| |||