תורת החישוביות/סיבוכיות קולמוגורוב: הבדלים בין גרסאות בדף
תוכן שנמחק תוכן שנוסף
שורה 296:
<math>x</math>
באופן הבא:
# תיאור כ"א מ<math>\sqrt n - 1</math> האפשרויות של כל אחד מ<math>\frac{2n}{\log(n)}</math> החלקים
(\sqrt(n) - 1)^{\frac{2n}{\log(n)}}
# תיאור מ"ט הבונה את המחרוזת מהתיאורים הנ"ל - ▼
\right)
</math> תווים.
▲# תיאור מ"ט הבונה את המחרוזת מהתיאורים הנ"ל - את זאת אפשר לעשות בעזרת <math>O(1)</math> תווים.
גם כאן נקבל
<center><math>
n - p \leq K(x) \leq O(1) +
| |||