Швидке зведення в ступінь - це

оцінка складності

Щоб дізнатися, скільки умножений потрібно для зведення числа x в ступінь n алгоритмом швидкого зведення в ступінь, потрібно зробити обчислення за такою формулою: k = H + 2 (E - 1). де H - кількість нулів, а E - кількість одиниць в двійковій запису числа n.

Так, для зведення числа в соту ступінь цим алгоритмом буде потрібно всього лише 8 умножений.

Таким чином кількість множень одно O (lnn).

Ми можемо назвати операцію * множенням і визначити операцію піднесення до натурального степеня:

Для обчислення значень a n можна використовувати алгоритм швидкого зведення в ступінь.

література

Дивитися що таке "Швидке зведення в ступінь" в інших словниках:

Алгоритм швидкого зведення в ступінь - алгоритм швидкого зведення в ступінь алгоритм, призначений для зведення числа x в натуральну ступінь n за менше число множень, ніж це потрібно в визначенні ступеня. Алгоритм не завжди оптимальний: наприклад, швидке зведення ... ... Вікіпедія

Програмовані алгоритми - Службовий список статей, створений для координації робіт з розвитку теми. Дане попередження не встановлюють нові ... Вікіпедія

Логарифм - Графік довічного логарифма логарифм числа ... Вікіпедія

Алгебра - Загальні відомості Алгебра один з великих розділів математики (Див. Математика), що належить поряд з арифметикою (Див. Арифметика) і геометрією (Див. Геометрія) до числа найстаріших гілок цієї науки. Завдання, а також методи А., ... ... Велика радянська енциклопедія

Німеччина - Федеративна Республіка Німеччини (ФРН), держ під в Центр. Європі. Німеччина (Germania) як територія, заселена герм, племенами, вперше згадується Пифеем з Массалии в IV ст. до н. е. Пізніше назва Німеччина використовувалося для позначення рим. ... ... Географічна енциклопедія

Толстой, граф Лев Миколайович - знаменитий письменник, який досяг ще небувалою в історії літератури XIX в. слави. В його особі могутньо з'єдналися великий художник з великим моралістом. Особисте життя Т. його стійкість, невтомність, чуйність, одухотворення у відстоюванні ... ... Велика біографічна енциклопедія