时间复杂度
时间复杂度
数据结构/算法
1、什么是时间复杂度
时间复杂度是某个算法的时间消耗，他是该算法所求问题规模n的函数。而渐进时间复杂度是指当问题规模趋向于无穷大时，该算法时间复杂度的数量级。通常我们在计算的算法的时间复杂度为T(n)=O(f(n)).通常我们总是考虑最坏情况下的时间复杂度
常见的时间复杂度有：常数O(1),对数O(logn),线性O(n),O(nlogn),平方O(n^2),k次方O(n^k),指数O(2^n)
2、时间复杂度例子
for (i = 0; i & ++i)
for (j = 0; j & ++j)
sum += a[i][j]
while (i &= n)
3、计算方法
先找出基本的操作；
找到各语句执行次数；
然后将各个语句时间复杂度相加。
最后转换为大O计法(和高等数学里的无穷小和无穷大相似)
4、递归时间复杂度
当一个算法里面包含递归时，计算复杂度的问题或转化为求解递归方程的问题。
常用的解法有如下几种：
迭代地将递归方程展开，使之成为一个非递归的和式，然后通过对和式的估计来达到对方程左端即方程的解的估计。
某算法的计算时间为：T(n) = 3T(n/4) + O(n)，其中T(1) = O(1)，迭代两次可将右端展开为：
T(n) = 3T(n/4) + O(n)
= O(n) + 3( O(n/4) + 3T(n/42 ) )
= O(n) + 3( O(n/4) + 3( O(n/42 ) + 3T(n/43 ) ) )
从上式可以看出，这是一个递归方程，我们可以写出迭代i次后的方程：
T(n) = O(n) + 3( O(n/4) + 3( O(n/42 ) + … + 3( n/4i + 3T(n/4i+1 ) ) ) )
当n/4i+1 =1时，T(n/4i+1 )=1，则:
T(n) = n + (3/4) + (32 /42 )n + … + (3i /4i )n + (3i+1 )T(1) & 4n + 3i+1
T(n) = n + (3/4) + (32 /42 )n + … + (3i /4i )n + (3i+1 )T(1) & 4n + 3i+1
而由n/4i+1 =1可知，i
T(n) = 2T(n/2) + n2
　　迭代2次可以得：
　　T(n) = n2 + 2(2T(n/4) + (n/2) 2)
　　还可以继续迭代，将其完全展开可得：
　　T(n) = n2 + 2((n/2) 2 + 2((n/22)2 + 2((n/23) 2 + 2((n/24) 2 +…+2((n/2i) 2 + 2T(n/2i + 1)))…))))　　……(1)
　　而当n/2i+1 == 1时，迭代结束。
　　将(1)式小括号展开，可得：
　　T(n) = n2 + 2(n/2)2 + 22(n/22) 2 + … + 2i(n/2i)2 + 2i+1T(n/2i+1)
　　这恰好是一个树形结构，由此可引出递归树法。
图中的(a)(b)(c)(d)分别是递归树生成的第1,2,3,n步。每一节点中都将当前的自由项n2留在其中，而将两个递归项T(n/2) + T(n/2)分别摊给了他的两个子节点，如此循环。
　　图中所有节点之和为:
　　[1 + 1/2 + (1/2)2 + (1/2)3 + … + (1/2)i] n2 = 2n2
　　可知其时间复杂度为O(n2)
可以得到递归树的规则为：
　　(1) 每层的节点为T(n) = kT(n / m) + f(n)中的f(n)在当前的n/m下的值；
　　(2) 每个节点的分支数为k；
　　(3)每层的右侧标出当前层中所有节点的和。
　　T(n) = T(n/3) + T(2n/3) + n
　　其递归树如下图所示：
我的热门文章
即使是一小步也想与你分享求助各位高手一道题！！利用递归树来找出递归式T(n)=T(n-a)+T(n-a)+cn的渐近紧确解，其中a& =1且c& 0是常数。 & 请各位帮助 & 不甚感激！！
回答1：t(n)=n^(1/2)*t(n^(1/2))+n
t(n^(1/2)=n^(1/4)*t(n^(1/4))+n^(1/2)
代价：n^(1/2)*n^(1/2)==n
t(n^(1/4)=n^(1/8)*t(n^(1/8))+n^(1/4)
代价：n^(1/2)*n^(1/4)*n^(1/4)==n
t(n^(1/8)=n^(1/16)*t(n^(1/16))+n^(1/8)
代价：n^(1/2)*n^(1/4)*n^(1/8)*n^(1/8)==n
t(16)=4t(4)+16;
t(4)=2t(2)+4;
O(Nlog(logN))
songxiaofei
回答2：lgn-1
∑n/(logn-i) = n/logn + n/(logn-1) + ... + n/1 =
∑n/i = n∑1/i;
log(logn + 1)
其中易证------------- = & ∑1/i
&= --------- + 1,所以∑1/i =theta(log(logn)),
原来那个就是theta(nlog(logn))
songxiang233查看: 4779|回复: 14
关于4 Sum O(n^2logn)解法的问题
精华主题学分
勤奋农民-感谢提供高质量信息和讨论, 积分 773, 距离下一级还需 227 积分
在线时间 小时
注册一亩三分地论坛，查看更多干货！
才可以下载或查看，没有帐号？
Leetcode中4sum的题目是这样的：
Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.
Elements in a quadruplet (a,b,c,d) must be in non-descending order. (ie, a ≤ b ≤ c ≤ d)
The solution set must not contain duplicate quadruplets.
For example, given array S = {1 0 -1 0 -2 2}, and target = 0.
& & A solution set is:
& & (-1,&&0, 0, 1)
& & (-2, -1, 1, 2)
& & (-2,&&0, 0, 2)
我知道这题的O(n^3)的解法，不过网上很多人说给出了O(n^2logn)的算法, 但这些算法个人觉得实际上并没有处理好S中重复和的问题。比如这篇文章的讨论： 该文中Hash解法复杂度个人觉得并没有快于O(n^3)。
还有这里的解法：
以及这里的解法：
算法思路都是把所有pair的和以及相应两数的index存起来，将四数求和的问题转为二数求和。接下来一种思路是先将存起来的数排序(O(n^2 log n^2), 然后夹逼。注意夹逼时针对的数组中的每个元素实际上是两数和， 会有很多组合，所以如果夹逼时两元素和 == target， 还需要检查每个元素重复值所对应的两个数，这样一来因为一共有O(n^2)个元素，很有可能时间复杂度是O(n^4)。
另外一种思路是所有的pair和存到hashtable中。不过因为一个和可能对应多种组合，个人觉得应该用hash-multimap。这个具体代码在Leetcode题解（C++）版中给出了。 这个multimap里key是两数和，value是两数index，可能有多个，所以比较时也应该所有value对应的元素相互都比较才行，总复杂度感觉也不会是O(n^2)。
不知大家做过此题的人想法怎样。我说的可能不清楚，但很希望能和大家讨论一下此题。
精华主题学分
在线时间 小时
本帖最后由 Kimurate 于
18:44 编辑
感觉你写的有点乱，不知道是我饿着肚子的原因还是你没想清楚……
你给的第一个链接我看过，有些许错误信息，而且 k-sum 的代码逻辑至少在 java 版本是会超时。
讲讲正题。以下都是我个人理解，仅供参考，欢迎吐槽。
2 sum 的 hashtable 解法是不需要排序的，O(n) 就可以。
对 4sum 来说，排序是必须的，先 n log(n)，
在 LeetCode 里，4sum 要规约成 2sum + 2sum，我还没发现别的不超时的解法，所以这个解法是 O(nlogn + n^2 logn)
注意这里的 2sum 和单独 2sum 有所不同，我待会贴个链接。
早些年有论文指出，k-sum 问题的时间复杂度的理论下界大约是 N^(k/2) （具体我忘了，和 k 的奇偶有关），
其最快算法的思想即是把取 k 个数的问题看成取 k/2 个数，然后验证 sub-sum pair 的和是否是目标值。
我前些日子正好做了这道题，实现了这个算法，可以用同一段代码过 3 sum 和 4 sum。
k-sum 问题可说是好多 LeetCode 题目的结合版，写得超长，从 3sum 到 4sum 到 k-sum，没有一小时估计读不下来。
精华主题学分
在线时间 小时
感觉你写的有点乱，不知道是我饿着肚子的原因还是你没想清楚……
你给的第一个链接我看过，有些许错误信息 ...
谢谢你的链接，该文章讲得很赞，代码我看了看，算法应该是没问题的。不过能否解释一下算法复杂度为何是O(n^2logn)呢？当存在重复和时，实际执行时是三重for循环，worst case的时间似乎是n^3吧？( 下边代码的回复似乎也是同样意思）
精华主题学分
在线时间 小时
贴一下我的代码吧，最内层循环是个binary search，所以是O(lg(n))，再加上外层两个for循环，n^2lg(n)
精华主题学分
在线时间 小时
贴一下我的代码吧，最内层循环是个binary search，所以是O(lg(n))，再加上外层两个for循环，n^2lg(n)
最内循环不能叫binary search吧。。。while里边的本质上是双向夹逼，是线性时间，所以总共是O(n^3)的。Worst case是： S = { 1, 2, 3, 4, 5, 6}, target = 1000。
精华主题学分
在线时间 小时
最内循环不能叫binary search吧。。。while里边的本质上是双向夹逼，是线性时间，所以总共是O(n^3)的。Wo ...
你是对的，我搞错了，我那个的确还是O(n^3)的
精华主题学分
在线时间 小时
谢谢你的链接，该文章讲得很赞，代码我看了看，算法应该是没问题的。不过能否解释一下算法复杂度为何是O( ...
复杂度：2sum里，for循环中每次要 search，时间是 logn，所以2sum 复杂度应该是 O(nlogn)，我之前说错了。4sum里，外面套一个分割元素的循环，n，然后里面是并排的两个2sum，你可以把他们合成一个 n for来看，加上每次 containsKey 需要 log (n^2)（最多有 n^2 个元素），所以最终是n^2 log(n^2)，化成n^2 (2 log n)，去掉常数就可以了。
精华主题学分
在线时间 小时
谢谢你的链接，该文章讲得很赞，代码我看了看，算法应该是没问题的。不过能否解释一下算法复杂度为何是O( ...
关于重复的问题，我认为hash 的方法里总可能遇到最坏时间复杂度，也和hashtable的实现有关，不知道该怎么说
精华主题学分
在线时间 小时
复杂度：2sum里，for循环中每次要 search，时间是 logn，所以2sum 复杂度应该是 O(nlogn)，我之前说错了 ...
不知你说的是否是这个代码
这个代码里，内层两个并排的for循环不是问题，问题是在第一个内循环里边还有一个小循环:for (auto &p: hash[target - a]) {
& && && && && && && && &vector&int& b = {p.first, p.second, num&i&, num[j]};
& && && && && && && && &ans.insert(b);
& &}&/i&复制代码这里的p会遍历所有和为target - a的pair，当存在不知一组pair的时候，整体的复杂度就不是O(n^2logn)了吧。
我所说的重复就是这个，即当存在多组不同的数对但和是一样的时候，并不是hashtable里边那个collision。
精华主题学分
在线时间 小时
不知你说的是否是这个代码/discuss/3950/tle-on-4sum-using-hashtable
这个代 ...
key是2sum的值，那就还是hash碰撞，这里的hash有两层，第二层没碰撞罢了，但你说的这种值一样，元素组成都不一样的情况，不可能出现，因为数组已经经过排序
精华主题学分
在线时间 小时
本帖最后由 eaglesky1990 于
09:19 编辑
key是2sum的值，那就还是hash碰撞，这里的hash有两层，第二层没碰撞罢了，但你说的这种值一样，元素组成 ...
数组排好序了，和还是有可能是一样的吧？比如： S = {1, 2, 3, 4, 5, 6, 7, 8} 。 考虑i = 6 时，因为1+6 = 2+5 = 3+4 = 7, 所以对应于7的set里存在有三组pair，当j = 7, target = 22时,&&此时 a = S[6] + S[7] = 15, target - a = 7, hash[7]这个set里就有三组pair，第三层for循环就要跑三次了。换个角度看，如果这种和相同的情况没有，那也没有必要用set了吧, 第三层for循环又有什么意义呢？
精华主题学分
在线时间 小时
数组排好序了，和还是有可能是一样的吧？比如： S = {1, 2, 3, 4, 5, 6, 7, 8} 。 考虑i = 6 时，因为1+6 ...
咳咳，不可能的，你没仔细看那个c++代码的逻辑。
i=6时，不是1+6, 2+5, 3+4, 而是1+6, 2+6，3+6, ... 5+6, 所以一次循环里，不存在一个和对应多个二元组的情况。
用set是因为从[1,1,1,1,2,2,2] 取出和为6的四元组时，会有很多重复的四元组。
精华主题学分
在线时间 小时
咳咳，不可能的，你没仔细看那个c++代码的逻辑。
i=6时，不是1+6, 2+5, 3+4, 而是1+6, 2+6，3+6, ... 5+ ...
我的理解是： i 是 从 0 开始循环的， i 值达到 6 之前必然先经过5, 而i = 5 时 1+ 6, 2 + 6, 3 + 6 ... 5 + 6 被放入相应 i = 4 时是1 +&&5, 2 + 5, 3 + 5, 4 + 5 被放入相应set 。 所以 i = 6 时， hashtable中存有前边所有两两组合的pair, 这样做也才是保证不丢解。
精华主题学分
在线时间 小时
我的理解是： i 是 从 0 开始循环的， i 值达到 6 之前必然先经过5, 而i = 5 时 1+ 6, 2 + 6, 3 + 6 ...&&...
恩，有道理。这个O(n^3)应该是最坏情况，但即便从构造的例子中来看，这个情况也是非常局部的，不知道能否扩展到整体，把整个算法都变成O(n^3)。
两部分的2sum只会越来越大，和跟二元组不会总有很多重复的。感觉上重复二元组的数量好像是先从少变多，然后又变少了，应该不是O(n)，但我不知道怎么证明。
详细看看这个
好多细节我还是没搞懂啊 = =。
精华主题学分
在线时间 小时
我觉得关键是 如何在n^2logn复杂度下生成不含重复元素的 pairs
knuth好像有写过generate all combinations 我也没太懂，还希望lz多多指教指教，我想了半天实在没啥思路。。哭
<form method="post" autocomplete="off" id="fastpostform" action="forum.php?mod=post&action=reply&fid=84&tid=102515&extra=&replysubmit=yes&infloat=yes&handlekey=fastpost"
onSubmit="
// TODO Howard 11/3/2015
var sbtn = $('fastpostsubmit');
sbtn.disabled =
sbtn.innerHTML = ' 回复发表中... ';
sbtn.setAttribute('background', sbtn.style.background);
sbtn.setAttribute('bordercolor', sbtn.style.borderColor);
sbtn.style.background = '#C7C7C7';
sbtn.style.borderColor = '#8B8B8B';
var form =
// --product--
var isValid = fastpostvalidate(form, null, 0);
if(!isValid) reoverBtn();
return isV
// --product--
// --testing--
//setTimeout(function() {
// var isValid = fastpostvalidate(form, null, 0);
// if(!isValid) reoverBtn();
//}, 2000);
// --testing--
您需要登录后才可以回帖
回帖并转播
回帖后跳转到最后一页
Instant搜索更强大，不扣积分，内容组织的更好更整洁！目前仍在beta版本，努力完善中！
一亩三分地推荐 /5
地主Warald亲手做你的申请，针对你的背景和目标，考虑申请、学习、就业、移民等系列问题，制定申请策略。
“offer”指全额奖学金，免学费全免+每月工资，Berkeley, CMU, JHU, UIUC, Gatech, UMich, UCLA, Columbia，欢迎观赏。
电子工程、计算机、统计、金数金工、化工等, Stanford, Berkeley, CMU, Cornell, Yale, Columbia, Chicago, Duke, UPenn, UIUC, Brown, UMich, JHU等
有留学、申请、找工、职业规划上的难题？先上论坛提问！
论坛考古也帮不上忙，发帖得到的回答仍然不够？电话找Warald来解答！
WARALD新书上市啦：《你不知道的美国留学》清华大学出版社，各大电商发售
Powered byProblem:1430
Solution_ID:23134& && && && &\\t 与\\n
& && && && & & && &时间复杂度：Θ（) 空间复杂度：Θ（)
#include&iostream&int main(){int a,flag=1;
for(int j=2;j&a;j++)
if(a%j==0)
if(flag==1)
cout&&"&a href="file://\\t"&\\t&/a&";
else cout&&"&a href="file://\\n"&\\n&/a&";
return 0;}
by 47177 十一月 9,
Solution_ID:22732& && && && &坑人的反斜杠。。。
& && && && & & && &时间复杂度：Θ（) 空间复杂度：Θ（)
#include&iostream&#include&cstdio&char x=92;int main(){
bool b=1; cin&&a; for(int i=2;i*i&=a;i++)
if(a%i==0)b=0; if(b)cout&&x&&'t'; else cout&&x&&'n'; return 0; }
by 47698 十月 30,
Solution_ID:22683& && && && &c++
& && && && & & && &时间复杂度：Θ（) 空间复杂度：Θ（)
#include&cstdio&#include&iostream&int main(){
scanf("%d",&n); if(n==1 || n==0)
printf("\\n");
return 0; } for(int i=2;i*i&=n;i++)
if(n%i==0)
printf("\\n");
} printf("\\t"); return 0;}
by 47652 十月 28,
Solution_ID:22603& && && && &看到同学用了机智的办法2.0
& && && && & & && &时间复杂度：Θ（) 空间复杂度：Θ（)
这里写题解……刚刚的写错了(●ˇ?ˇ●)忘加等号了，重来#include&stdio.h&#include&math.h&int main(void){ int i, count=0, scanf("%d",&n); for(i=2; i&=sqrt(n); i++) {
if(n%i==0) count++; } if(count==0&&n!=1) printf("\\t\n"); else printf("\\n\n"); return 0;}
by 45134 十月 26,
Solution_ID:22602& && && && &看同学用了机智的办法
& && && && & & && &时间复杂度：Θ（) 空间复杂度：Θ（)
这里写题解#include&stdio.h&#include&math.h&int main(void){ int i, count=0, scanf("%d",&n); for(i=2; i&sqrt(n); i++) {
if(n%i==0) count++; } if(count==0&&n!=1) printf("\\t\n"); else printf("\\n\n"); return 0;}
by 45134 十月 26,
Solution_ID:22595& && && && &int fuck,
& && && && & & && &时间复杂度：Θ（mdzz) 空间复杂度：Θ（n^00)
fuck vs shit
boom.................
by 45043 十月 26,
Solution_ID:22503& && && && &小小观点仅供 参考
& && && && & & && &时间复杂度：Θ（) 空间复杂度：Θ（)
#include&iostream&int main(){
int x,f=0,i;
for(i=2;i&x;i++){
if(x%i==0) {
cout&&"\\n";
cout&&"\\t";
by 45225 十月 22,
Solution_ID:22422& && && && &线性筛
& && && && & & && &时间复杂度：Θ（o（n）) 空间复杂度：Θ（)
#include&iostream&#include&cstdio&#include&cstring&int main() { static int cnt=0,n,prime[100010]; static bool not_prime[100010]; cin&&n; memset(not_prime,0,sizeof(not_prime)); not_prime[1]=1; for(int i=2; i&=n; i++) {
if(!not_prime[i])prime[++cnt]=i;
for(int j=1; j&= j++) {
if(prime[j]*i&n)
not_prime[prime[j]*i]=1;
if(!(i%prime[j]))
} } if(not_prime[n])printf("\\n"); else printf("\\t");}
by 41889 十月 20,
Solution_ID:22249& && && && &ninmik
& && && && & & && &时间复杂度：Θ（) 空间复杂度：Θ（)
Author:sslz-grh#include&iostream&#include&cstdio&int e(int h){ for(int i=1;i&=h;++i) if(h&=i*i&&h&=(i-1)*(i-1)) }int main(){
cin&&g; for(int j=2;j&=e(g);++j) {
if(g%j==0)
printf("\\n");
printf("\\t"); return 0;}
by 42331 十月 16,
Solution_ID:22161& && && && &mdzz
& && && && & & && &时间复杂度：Θ（O(1/n)) 空间复杂度：Θ（O(n*n*n*n*n*n*))
这里写题解mdzzmdzzmdzzmdzzmdzzmdzzmfzzmdZz
by 46613 十月 14,
Solution_ID:22070& && && && &Eratosthenes筛选法
& && && && & & && &时间复杂度：Θ（nloglogn) 空间复杂度：Θ（n)
#include &iostream&#include &cmath&int ar[30001]={1,1,0};int main(){
int m=sqrt(a)+0.5;
for(int i = 2;i&=m;++i)
if(!ar[i])
for(int j=i+i;j&=a;j+=i)
ar[j]=1;//is not 素数
cout && (ar[a]?"\\n":"\\t") && }
by 29731 十月 10,
Solution_ID:22009& && && && &C++ 欧拉筛
& && && && & & && &时间复杂度：Θ（o(nlogn)) 空间复杂度：Θ（.....)
#include&cstdio&#include&cmath&bool vis[30105];int main(){scanf("%d",&n);int m=sqrt(n);for(int i=2;i&=m;i++)if(!vis[i])for(int j=i*i;j&=n;j+=i)vis[j]=if(vis[n])printf("\\n");else printf("\\t");return 0;}
by 33409 十月 8,
Solution_ID:21978& && && && &wsmzjzz
& && && && & & && &时间复杂度：Θ（) 空间复杂度：Θ（)
#include &iostream&#include &cmath&bool is_prime(int);int main(){
cin && cout && (is_prime(n) ? "\\t" : "\\n") && return 0;}bool is_prime(int n){ bool flag = for (int i = 2; i &= sqrt(n); ++i)
if (n % i == 0)
by 41285 十月 7,
Solution_ID:21671& && && && &pascal
& && && && & & && &时间复杂度：Θ（) 空间复杂度：Θ（)
var a,n,x,y,i:begin readln(a); x:=0; y:=0; if (a=0) or (a=1) then writeln('\t'); if a=2 then writeln('\n'); if a&2 then begin
n:=round(a/2);
for i:=2 to n do begin
if (a mod i)=0 then y:=y+1
else x:=x+1;
if x=n-1 then writeln('\t');
if y&0 then writeln('\n');end.
by 36612 九月 27,
Solution_ID:21670& && && && &pascal
& && && && & & && &时间复杂度：Θ（) 空间复杂度：Θ（)
var a,n,x,y,i:begin readln(a); x:=0; y:=0; if (a=0) or (a=1) then writeln('\t'); if a=2 then writeln('\n'); if a&2 then begin
n:=round(a/2);
for i:=2 to n do begin
if (a mod i)=0 then y:=y+1
else x:=x+1;
if x=n-1 then writeln('\t');
if y&0 then writeln('\n');end.
by 36612 九月 27,
Solution_ID:21466& && && && &一起喝尿
& && && && & & && &时间复杂度：Θ（) 空间复杂度：Θ（o(n^2))
by 42554 九月 19,
Solution_ID:21136& && && && &pascal
& && && && & & && &时间复杂度：Θ（) 空间复杂度：Θ（)
var n,i,j:beginreadln(n);j:=0;for i:=2 to trunc(sqrt(n)) doif n mod i=0 then inc(j);if j&=1 then writeln('\n') else writeln('\t');end.
by 43821 九月 3,
Solution_ID:20893& && && && &简单AC
& && && && & & && &时间复杂度：Θ（) 空间复杂度：Θ（)
#include&iostream&#include&algorithm&int main(){
int a,n,flag=1;
for(a=2;a*a&=n&&a++)
if(n%a==0)
cout&&"\\t";
cout&&"\\n";
return 0;}
by 20057 八月 21,
Solution_ID:20760& && && && &很简单而且很短
& && && && & & && &时间复杂度：Θ（O根号N) 空间复杂度：Θ（)
#include&iostream&#include&cstdio&int main(){
int n,l=1;
scanf("%d",&n);
for(int i=2;i*i&=n;i++) if(n%i==0) {l=0;}
if(l==1) puts("\\t");
else puts("\\n");}
by 43648 八月 17,
Solution_ID:20730& && && && &容易理解
& && && && & & && &时间复杂度：Θ（) 空间复杂度：Θ（)
#include&iostream&int x,int main(){ cin && for (int i = 1; i &= i++)
for (int j = 1; j &= j++)
if (i*i == x)sum++;
if (i*j == x)sum++;
} sum /= 2; if (sum == 1)cout && "\\t"; else cout && "\\n"; return 0;}
by 43533 八月 16,：转载时请以超链接形式标明文章原始出处和作者信息及本声明
算法原理：对于对偶(Fib(n+1),Fib(n))---&变换T---&(Fib(n+2),Fib(n+1)),
例如：(1,0)--&(1,1)--&(2,1)--&(3,2)--&......
显然变换T：
(a,b)--&T--&(a+b,a)
而斐波那契数列可由对偶(1,0)（也就是(Fib(1),Fib(0)）经过n次T变换产生(Fib(n+1),Fib(n))；
现在将T看作是变换簇Tpq的一个特列：
(a,b)--&Tpq--&(bq+aq+ap,bp+aq)
当p=0,q=1时候变换T01就是前面所提到变换T;
下面证明这个变换簇的一个奇特的特性：
存在变换Tij = Tpq*Tpq:也就是证明：
对偶(a,b)--&Tpq--&(bq+aq+ap,bp+aq)--&Tpq--&(b(q*q+2pq)+a(2q*q+2pq+p*p),b(p*p+q*q)+a(q*q+2pq)),
(a,b)--&Tij--&(b(q*q+2pq)+a(2q*q+2pq+p*p),b(p*p+q*q)+a(q*q+2pq)),
显然可以取i=p*p+q*q,
& & & & & & & j =&q*q+2
可以得到变换Tij = Tpq*T
**************************************************************************
由于这个特性：(1,0)--&n次T--&((Fib(n+1),Fib(n));
n次变换太多，可以当n为偶数的时候，可以用n/2次应用Tij来代替之，所以有下面的算法：
(define (fib n)
& & (fib-iter 1 0 0 1 n))
(define (fib-iter a b p q count)
& & &(cond ((= count 0) b)
& & & & & & & ((even? count) (fib-iter a b (+ (square p) (square q)) (+ (square q) (* 2 p q)) (/ count 2)))
& & &(else (fib-iter (+ (* b p) (* a p) (* a q))
& & & & & & & & & & & & &(+ (* b p) (* a q))
& & & & & & & & & & & & &p
& & & & & & & & & & & & &q
& & & & & & & & & & & & &(- count 1)))))
其中even? square
(define (even? n)
& & (= (remainder n 2) 0))
(define (square x) (* x x))
算法解释：先判断n为偶数时候，需要迭代n次T变换，可以用n/2次Tij变换来代替，当n为奇数，可先做一次变换，减少一次变换，是的变换次数为偶数。
算法复杂度O(logn)
访问统计：