Combinações em C

[Simao]

Existe alguma função para calcular combinações em C?


É que calcular à pata tem uma complexidade temporal brutal para números grandes

Obrigado.

 

[Rui_Carlos]

mesmo que o C tenha uma função para calcular combinações, a complexidade não deve ser mais pequena do que numa função implementada por ti...
e assim à primeira vista a complexidade é "apenas" linear no tamanho do número maior.

mas se não precisares de valores exactos (até porque dada a dimensão dos números vais ter que usar float/double, logo nunca vais ter valores exactos) pode fazer as coisas de uma forma mais eficiente, usando esta função para calcular o factorial dos valores: http://en.wikipedia.org/wiki/Stirling's_formula

 

[Simao]

A complexidade seria exponencial, visto que tinha q calcular 3 factoriais.
A não ser que usasse programação dinamica.

Obrigado pela ajuda, ja resolvi o meu problema.

 

[Rui_Carlos]

admitindo que o tempo que uma multiplicação demora a ser realizada é constante a complexidade era linear.

o factorial de n seria um ciclo de n iterações, logo é linear no tamanho do número.
ter que calcular 3 factoriais ou 1 (ou 10 ou 100 ou outro valor qualquer desde que seja fixo) não altera a complexidade do problema (O(3n)=O(n)=O(10000n)=...).
e por acaso só preciavas de calcurar o factorial do maior número, os outros 2 podiam ser determinados no cálculo do maior.