Question

数据结构中的时间复杂度和空间复杂度怎么样理解？

人们通常采用大O来表示法来描述分析的结果。如果存在正的的常数M和N0,当问题的规模N大于或等于N0后，算法的时间度T（n）小于或等于M·f（n），那么就称算法的时间复杂度为O（f（n））。这种说法意味着`当N充分大时，该算法复杂度不大于f（n）的一个常数倍！ 这个怎么理解啊？

Answer 1

时间复杂度为O（f（n））说的是算法的时间T（n）随n的增长与函数f(n)的增长速度相同，这里的"相同"应这样理解，比如n增长变为原来的两倍，T(n)与f(n)都变为原来的K倍（增长相同）。如：T（n）=n^2+n+2=O(n^2)的复杂度是说，n变为原来的两倍，T（n)就变为原来的4倍(n足够大时)。……这里的大O表示时间复杂度只是T（n）的一个上限，即最坏情况，但习惯上都考虑这种情况。