תורת החישוביות/סיבוכיות קולמוגורוב: הבדלים בין גרסאות בדף
תוכן שנמחק תוכן שנוסף
←אי-דחיסות מחרוזות: הרחבה |
|||
שורה 173:
==יישום: חסמים תחתונים לסיבוכיות אלגוריתמים==
[[#אי-דחיסות מחרוזות|אי-דחיסות מחרוזות]] משמש לעתים להוכחת חסמים תחתונים על זמני הריצה של [[מבני נתונים ואלגוריתמים - מחברת קורס/אלגוריתמים/סדרי גדילה|סיבוכיות]] אלגוריתמים. הרעיון הכללי הוא כזה. בהנתן קלט <math>x</math> כלשהו, מראים שאלגוריתם "יעיל מדי" הפועל עליו, מניב תיאור קצר במיוחד שלו, בסתירה לכך שלכל אורך נתון, יש לפחות מחרוזת אחת בלתי דחיסה לחלוטין.
===שימוש להוכחת חסם תחתון על סיבוכיות מציאת פלינדרום===
|