蜻蜓
提示 登录 注册 提示 13269/0 09年1月6日 周二 14点53分 站标
从二品:光禄大夫|镇军大将军级别

头像 积分:33820 乐善:291 声望:1495
离线/隐身 无斋主人 家园博客 发短信
注册于:2003-12-12 19:08:38
大类:[科技经济] → 版面:[科经茶社]
818/29 转发回复分页全看树展楼主帖 引用0 送花10收藏:0工具
o这比用一个临时变量,记住长度效率差多了 [ 无斋主人 ] 于:2007-03-29 17:08:45
void reverse(char *p)
{
    int cnt = 0;
    
    // calculate length
    while (p[cnt] != 0) ++cnt;

    while ((cnt>>1) > 0)
    {
       // switch first and the last
       *p ^= p[cnt-1] ^= *p ^=p[cnt-1];
        
       p++;
       // cuz p moved forward, we have to minus 2
       cnt -= 2;
    }
}

您老看看,算长度,n, 交换位置1/2n,总共O(n)。只用一个临时变量。

递归算法,
1)要是N很大,stack就爆掉了,
2)而且每次调用函数,必须push ebp,调整ebp,压入参数,还要记住retern addr, jump回来,clean stack。浪费无数。
3)时间复杂度上,递归算法是O(n^2)

就为省一个临时变量。

现实生活中,谁要这么写程序,真可以直接fire了。出这种题的也应该fire,纯粹误导。



最后于2007-03-29 17:26:40改,共2次;
818/29/0 转发回复分页全看树展楼主帖 引用0 送花10收藏:0工具
引用(0) 请拷贝:
※※※ 相关(回复)帖 ※※※
。。O 老成都的code的复杂度不是变成了 (tingsanguo;字72 阅562
。。。O 有那么高吗?n平方吧?我的倒是指数增长的 (林小筑;字0 阅525
O 递归解法 (泰让;字91 阅1094 花2
。。O code出来了,谢谢帮忙,CODE在内, (老成都;字357 阅1190 花3
。。。O 这比用一个临时变量,记住长度效率差多了(无斋主人;字687 阅818 花1 O
。。。。O 这道明显是brain teaser,又不是编程题,限制条件列得 (林小筑;字222 阅274 花1
。。。。。O 花一个!问题是俺们这些老蓝领反应已经很慢了, (老成都;字241 阅266 花1
。。。。O 把 int cnt 换成 char *end, 然后 (tingsanguo;字64 阅248 花1
... 共 》29《跟帖
~~~◇—签 名 档—◇~~~

宠辱不惊,闲看庭前花开花落
~~~————~~~
广告 购物分成,帮助网站

点这里自动刷新◆ 或者 完整聊天

英雄榜 前十名(左栏新兵,右栏全站)
Che
流川
曲里拐弯
羽羊
奥森
暗香疏影月黄昏
北京地主
西洋镜
秋原
逐日夸父
蝶舞春园
故园湾里
北宸
抱朴仙人
1001n
大煮
wsxx
九霄环佩
aokrayd
亦无用

Copyright © cchere 西西河 feed 西西河规 版主规范 帮西西河 帮助(FAQ) 版面介绍 发帖特殊效果 网站地图 关于西西河