תורת החישוביות/סיבוכיות קולמוגורוב: הבדלים בין גרסאות בדף

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