时间复杂度 - 编程论坛

#2

azzbcc2015-10-21 09:19

我解释为分析代码的效率

比如:

程序代码：

#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倍,这就是时间复杂度的作用.

#3

azzbcc2015-10-21 09:37

程序代码：

#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编辑过]

#4

azzbcc2015-10-21 09:39

总的来说呢,时间复杂度和空间复杂度是算法性能的两个指标,对于同样的功能,两个指标越小,算法越好.

#5

qq16251273172015-10-22 09:32

好吧~~~