tft每日頭條

 > 生活

 > 簡單幂的運算

簡單幂的運算

生活 更新时间:2024-08-22 17:49:36

在m和n都屬于正數,并且m的n次方不超過LONG_MAX的情況下,如何求出m的n次方呢?一般都會想到用一個循環,如下

long result = 1;

for (int i = 0; i < n; i )

result * = m;

result即為所求,算法複雜度O(n)。這樣也能工作,但是當m和n變大時,效率會相當低下,如何優化呢?考慮2的4次方的情況,其實就是4個2相乘法;有沒有看出撒問題呢?是的,重複計算!前二個2相乘的結果可以直接用,後面兩個2的相乘不用再計算,即是

2X2X2X2 = 4X4

考慮2的5次方,即5個2相乘的情況,同樣的道理

2X2X2X2X2 = 4X4X2

所呈現出來的規律即是

m的n次方,在n為偶數時,可以變成 m的n/2次方的平方;在n為奇數時,則有n - 1為偶數,則變成m的(n-1)/2次方的平方再乘以m, 從n變成n/2,問題規模變小,中間計算結果可重複利用,可用遞歸解決,其算法複雜度變成O(logn)。具體代碼見下:

簡單幂的運算(快速幂運算)1

運行結果如下

簡單幂的運算(快速幂運算)2

,

更多精彩资讯请关注tft每日頭條,我们将持续为您更新最新资讯!

查看全部

相关生活资讯推荐

热门生活资讯推荐

网友关注

Copyright 2023-2024 - www.tftnews.com All Rights Reserved