蜻蜓
站标 提示 登录 忘了密码 注册 提示 10年3月18日 周四 10点40分
正二品:特进|辅国大将军级别

认证会员

头像 积分:36855 乐善:292 声望:1691
无斋主人 离线/隐身 家园 短信 加友 屏蔽
注册:2003-12-12 19:08:38

大类:新兵营地→版面:新兵科经/入选/候选

991/29 转发回复分页全看树展楼主帖 10宝推收藏:0统计更多工具
o这比用一个临时变量,记住长度效率差多了 [ 无斋主人 ] 于:2007-03-29 17:08:45 复:984467
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次;
991/29 转发回复分页全看树展楼主帖 10宝推收藏:0统计更多工具
被引用(1) 请拷贝:
※※※ 相关(回复)帖 ※※※
..O 老成都的code的复杂度不是变成了 tingsanguo 字72 阅683 2007-03-29 01:13:26
...O 有那么高吗?n平方吧?我的倒是指数增长的 林小筑 字0 阅646 2007-03-29 14:13:22
O 递归解法 花2 泰让 字91 阅1210 2007-02-18 18:47:22
..O code出来了,谢谢帮忙,CODE在内, 花3 老成都 字357 阅1329 2007-02-18 19:45:37
...O 这比用一个临时变量,记住长度效率差多了 花1 O 无斋主人 字687 阅991 2007-03-29 17:08:45
....O 这道明显是brain teaser,又不是编程题,限制条件列得 花1 林小筑 字222 阅363 2007-03-29 19:18:22
.....O 花一个!问题是俺们这些老蓝领反应已经很慢了, 花1 老成都 字241 阅342 2007-03-29 19:32:53
....O 把 int cnt 换成 char *end, 然后 花1 tingsanguo 字64 阅331 2007-03-29 18:58:41
... 共 》29《跟帖
Amazonɳ

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