תורת החישוביות/סיבוכיות קולמוגורוב: הבדלים בין גרסאות בדף
תוכן שנמחק תוכן שנוסף
מ ←שימוש להוכחת חסם תחתון על סיבוכיות מציאת פלינדרום: קישורים פנימיים |
|||
שורה 231:
אם כך קבלנו שמתקיים
<math>K(x) \leq \log_{|\Sigma|}(n) + \log_{|\Sigma|}(i) + c \frac{t(n)}{n}</math>
מצד שני מ[[
<math>K(x) \geq |x| = 3n</math>
משילוב שני האי-שוויונים, נקבל
| |||