Генерация сочетаний

[el_gato_de_Ch]

Всем привет. Давеча решал вот эту задачку на генерацию сочетаний, казалось бы ничего сложного. Сперва решил делать рекурсией.

вот решение

#include <iostream>

using namespace std;

int k,n;

int s[100];

void seq_gen(int, int);

int main()
{
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
	
	cin >> n >> k;
	
	seq_gen(0, 0);
	
	return 0;
}

void seq_gen(int lvl, int vmax)
{		
	if(lvl >= k)
	{
		for(int i = 0; i < k; ++i)
			cout << s[i] << " ";
		cout << endl;
	} else
	{	
		for(int j = vmax + 1; j <= n; ++j)
		{
			s[lvl] = j;
			seq_gen(lvl + 1, j);
		}
	}
}

получил time limit на 3х тестах. Я подумал что долго работает возможно из-за рекурсии, поэтому решил генерить сочетания последовательно. Соответственно получилось вот такое решение:

#include <iostream>

using namespace std;

int k,n;

int s[100];

int main()
{
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
	
	cin >> n >> k;
	
	for(int i = 0; i < k; ++i)
		s[i] = i + 1;
		
	if(k > n) return 0;
	
	do
	{
		for(int i = 0; i < k; ++i)
			cout << s[i] << " ";
		cout << endl;
		
		
		if(++s[k - 1] <= n) continue;
		if(k == 1) break;
		
		int ind = -1;
		for(int i = k - 2; i >= 0; --i)	
			if(s[i] <= n - k + i)
			{
				ind = i;
				break;
			}
		
		if(ind == -1) break;
		
		++s[ind];
		for(int i = ind + 1; i < k; ++i)
			s[i] = s[i - 1] + 1;
	} while(1);
	
	return 0;
}

и оно зашло, но у меня возник вопрос. Разве у алгоритмов не одинаковая асимптотическая сложность, я же ведь в лоб генерирую каждую перестановку, так почему 3 теста получили превышение по времени?

[RussDragon]

Рекурсия требует гораааздо больше ресурсов компьютера, особенно в цикле. Если я правильно понял код.