| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 2153 人关注过本帖
标题:时间复杂度
只看楼主 加入收藏
qq1625127317
Rank: 6Rank: 6
等 级:等待验证会员
威 望:1
帖 子:185
专家分:450
注 册:2015-9-3
结帖率:83.33%
收藏
 问题点数:0 回复次数:4 
时间复杂度
就是在学习数据结构时,就第一章的时间复杂度和空间复杂度,我就弄不明白了。。。到底表达的是什么意思了?有什么用呢?哎。。。
搜索更多相关主题的帖子: 空间 
2015-10-21 08:50
azzbcc
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:江西财经大学
等 级:贵宾
威 望:81
帖 子:3293
专家分:12919
注 册:2012-11-4
收藏
得分:0 
我解释为分析代码的效率

比如:
程序代码:
#include <stdio.h>

// 时间复杂度O(n)
int fun1()
{
    int sum = 0;

    for (int i = 1;i <= 100;i++)
    {
        sum += i;
    }

    return sum;
}

// 时间复杂度O(n/2)
int fun2()
{
    int sum = 0;

    for (int i = 1;i <= 50;i++)
    {
        sum += i + (101 - i);
    }

    return sum;
}

// 时间复杂度O(1)
int fun3()
{
    return (1 + 100) * 100 / 2;
}

int main(int argc, char *argv[])
{
    printf("%d\n", fun1());
    printf("%d\n", fun2());
    printf("%d\n", fun3());

    return 0;
}


这三个函数的功能是一样的,但可以明确的是fun3的效率是最高的.而对于fun1和fun2,可以说fun2的效率是fun1的2倍,这就是时间复杂度的作用.


[fly]存在即是合理[/fly]
2015-10-21 09:19
azzbcc
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:江西财经大学
等 级:贵宾
威 望:81
帖 子:3293
专家分:12919
注 册:2012-11-4
收藏
得分:0 
程序代码:
#include <stdio.h>

#define MAX  10

// 空间复杂度O(n^2)
int fun1(int m, int n)
{
    int sa[MAX][MAX] = {{0}};

    for (int i = 0;i <= m;i++)
    for (int j = 0;j <= i;j++)
    {
        if (j == 0 || j == i)  sa[i][j] = 1;
        else  sa[i][j] = sa[i-1][j-1] + sa[i-1][j];
    }

    return sa[m][n];
}

// 空间复杂度O(n)
int fun2(int m, int n)
{
    int sa[MAX] = {0};

    for (int i = 0;i <= m;i++)
    for (int j = i;j >= 0;j--)
    {
        if (j == 0 || j == i) sa[j] = 1;
        else  sa[j] = sa[j] + sa[j - 1];
    }

    return sa[n];
}

// 空间复杂度O(x)
int fun3(int m, int n)
{
    if (0 == n || n == m)  return 1;
    return fun3(m - 1, n) + fun3(m - 1, n - 1);
}

int main(int argc, char *argv[])
{
    printf("%d\n", fun1(6, 3));
    printf("%d\n", fun2(6, 3));
    printf("%d\n", fun3(6, 3));

    return 0;
}


还是同样功能的三个函数. fun2的sa是一维数组,空间复杂度O(n). fun1的sa是二维数组,空间复杂度O(n^2). 可以说fun2很大程度上优化了fun1算法.

至于fun3,递归算法的空间复杂度可以了解一下,它的空间复杂度为O(x).x为它被调用的次数,如fun3(6,3)函数本身被调用39次,则复杂度为O(39)

[此贴子已经被作者于2015-10-21 09:46编辑过]



[fly]存在即是合理[/fly]
2015-10-21 09:37
azzbcc
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:江西财经大学
等 级:贵宾
威 望:81
帖 子:3293
专家分:12919
注 册:2012-11-4
收藏
得分:0 
总的来说呢,时间复杂度和空间复杂度是算法性能的两个指标,对于同样的功能,两个指标越小,算法越好.


[fly]存在即是合理[/fly]
2015-10-21 09:39
qq1625127317
Rank: 6Rank: 6
等 级:等待验证会员
威 望:1
帖 子:185
专家分:450
注 册:2015-9-3
收藏
得分:0 
好吧~~~

从前风闻有你,现在我亲眼看见你
2015-10-22 09:32
快速回复:时间复杂度
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.028119 second(s), 7 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved