תורת החישוביות/סיבוכיות קולמוגורוב/הסתברות אוניברסאלית: הבדלים בין גרסאות בדף
תוכן שנמחק תוכן שנוסף
←קידוד ופענוח: הרחבה |
|||
שורה 118:
אורך הקידוד, לכן, הוא
<center><math>h + O(1) =
נשים לב כי,
<center><math>
K(x)
=
\log_{\left| \Sigma \right|}
\left(
\frac{1}{\left| \Sigma \right|^{-K(x)}}
\right)
\leq
\log_{\left| \Sigma \right|}
\left(
\frac{1}{\sum_{M \;|\; M(\epsilon) = x} \left| \Sigma \right|^{- \left| \langle M \rangle \right|} }
\right)
=
\log_{\left| \Sigma \right|}
\left(
\frac{1}{ P_U(x) }
\right)
</math></center>
| |||