数据结构中的
时间复杂度到底要怎么算的啊。
一直没有明白是怎么回事。。
看书也没有看明白。

希望大家指点一下。。。

从来不算...靠感觉,  复杂的算法也没写过

算法里才有时间复杂度吧？数据结构本身是没有的。

这个就是个数学问题，用来估算算法的时间成本。通常是用算法运算时间随参数量增大而增大的函数来表达。通常线性函数是最优的，但常常得不到这个结果。以排序算法来说，能够达到n*logn的级别就是优秀的了。当然也有例外，比如查找算法，很容易就可以做到对数函数的程度。

这个东西其实一般不需要计算，真要算的话，对于数学水平的要求就比较高了。

就是忽略常数，只考虑输入数据规模所对应的指数等级

比如冒泡排序

for (i=1; i<n; i++)
  for (j=i; j<n; j++)
  {   内部代码  }

我们可以看出内部代码被执行的次数是(n-1)+(n-2)+...1=1/2*n*(n-1)
所以时间复杂度是0.5*n*(n-1)*内部代码执行次数

由于内部代码执行次数是个常数，我们忽略掉，得出复杂度是n*(n-1)=n^2-n,同时我们忽略掉较低的指数级，所以最终时间复杂度是O(n^2)

然后说说为什么忽略常数和较低的指数级：
就说O(0.5n^2)和O(10000n)这两个复杂度哪个比较优秀，你可以得出当n<=某个数时第一个好，否则第二个好，但是我们可以看到当n小的时候运算时间很短可以忽略，而当n增大时第二个算法会优秀很多，所以常数相对来说没指数这么重要，同理由于指数的快速增长性，所以低指数也是可以忽略的

算法计算有很多方法，我最上面那直接算只是为了说明，一般来说都是直接估计的，看多了就会有经验的

挣分

楼主可以考虑下平均性态，也就是我们的加权平均或数学期望；或者是用最坏情况的复杂性，也就是最大运行次数。这两个结合起来能计算出来，或者估算出大概的时间复杂度

我今天刚学了时间复杂度，一般看的都是最坏时间复杂度，就是最坏情况下的时间复杂度。其实简单的想，时间复杂度就是一个程序的频度，即执行的次数。只要求执行次数最多的语句的频度就好了。

看是否有循环，循环中是否有嵌套循环！

谢谢你详细指点，，

關於複雜度，給你舉一個例子，看如下兩個版本的代碼：

void * memchr(void * pv, unsigned char ch, size_t size)
{
    unsigned char * pch = (unsigned char * )pv;
    unsigned char * pchEnd = pch + size;
    while (pch < pchEnd && *pch != ch) pch++;
    return ((pch < pchEnd) ? pch : NULL);
}

void * memchr(void * pv, unsigned char ch, size_t size)
{
    unsigned char * pch = (unsigned char * )pv;
    unsigned char * pchEnd = pch + size;
    while (pch < pchEnd)
    {
        if (*pch == ch) return (pch);
        pch++;
    }
    return (NULL);
}

你覺得哪個較好？