Блог пользователя Jackson

Автор Jackson, 11 лет назад, По-русски

Доброго времени суток. Может мне кто то доказать оценку сложности алгоритма Евклида? Спасибо.

  • Проголосовать: нравится
  • +7
  • Проголосовать: не нравится

»
11 лет назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

Теорема Ламе. Google it.

»
11 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

Зря минусуете. Не зная о теореме Ламе, трудно найти информацию в интернете об этом. Я например не нашел. Меня тоже этот вопрос заинтересовал, спасибо вышестоящему комментарию за ответ

»
11 лет назад, # |
Rev. 2   Проголосовать: нравится -10 Проголосовать: не нравится

есть такой вариант док-ва http://pmpu.ru/vf4/numtheory/lame. Хорошего строгого я не встречал, насколько помню. ну и есть логически-интуитивный. при условии, что вы как-то догадались, что числа Фибоначчи — худший случай (опять же логически-интуитивно понятно), то, исходя из их экспоненциального роста, логически-интуитивно понятен логарифм. но, лично я, сам бы не осилил... есть еще забавный математический факт, который тоже нетрудно понять: gcd(fib(i), fib(j)) = fib(gcd(i, j)).

  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Если вспомнить формулу Бине вместо второго включения интуиции, получится как раз теорема Ламе.

»
11 лет назад, # |
Rev. 5   Проголосовать: нравится +36 Проголосовать: не нравится

Попробую-ка я кратенько доказать. Пусть a > b. Рассмотрим два шага:

Так как a = kb + anew,  k ≥ 1,  anew < b ≤ kb, то и аналогично .

Таким образом после каждых двух шагов наша пара уменьшается не менее чем в 2 раза, а это уже не хуже, чем логарифмическая асимптотика.

Ну и легко показать, что для соседних чисел Фибоначчи F(n) и F(n + 1) количество итераций равно n + 1, что собственно и есть логарифм.

»
11 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Всем большое спасибо, вы мне очень помогли.

»
11 лет назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится

ну а в среднем какая оценка?
для случайных чисел меньших N

  • »
    »
    11 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    При прогоне до 10000, получил следующую оценку: 0.84·ln(n) - 0.44