一个简单的算法时间复杂度的有关问题

一个简单的算法时间复杂度的问题。
看书上有个题目是这样的：有一个算法T(n)=T(n-1)+n，T(1)=1。求T(n)的时间复杂度。
题目的答案是说因为T(n)实际计算的是1+2+3+...+n的值，根据公式它的值为(1+n)n/2所以时间复杂度为O(n^2)；
但是我认为T(n)的逻辑是通过递归依次将1到n相加，时间复杂度应该为O(n)。
求哪种正确。
------解决思路----------------------
Sigma( T(n)，2，n) =Sigma(T(n-1),1,n-1) +sigma(n,2,n)
于是
T(n) = T(1)+ sigma(n,2,n) =1+sigma(n,2,n) =sigma(n,1,n) = (n^2+n)/2 =O(N^2)
这个可以直接用数学方法计算出来的
------解决思路----------------------

引用:

Quote: 引用:

T(N)=O(N^2) 啊

可是要计算T(n)实际只进行了n-1次的递归和n-1次的加法运算，不觉得有O(n^2)的复杂度。

如果按公式算那下面这段代码岂不也是O(n^2)的复杂度？
int res = 1;

for(int i=1;i<=n;i++)

	res += i;



//实际代码

int T (int n) {

	if (n == 1)

		return 1 ;

	return T (n - 1) + n ;

}

//相当于

int _T (int n) {

	int _value ; //对应返回值寄存器

	stack<int> s ;

	s.push (n) ; //对应T (n)

	while (true) {

		if (s.top () == 1) { //对应n == 1

			_value = 1 ;

			s.pop () ; //对应return

			break ;	

		}

		s.push (s.top () - 1) ; //对应T (n - 1)

	} ;

	while (!s.empty ()) {

		_value = _value + s.top () ; //对应+ n

		s.pop () ; //对应return

	}

	return _value ;

}

毫无疑问复杂度O(n)
------解决思路----------------------
O（n^2) master 定理

一个简单的算法时间复杂度的有关问题

相关推荐