The standard Large Deviation Theory (LDT) represents the mathematical counterpart of the Boltzmann-Gibbs factor which describes the thermal equilibrium of short-range Hamiltonian systems, the velocity distribution of which is Maxwellian. It is generically applicable to systems satisfying the Central Limit Theorem (CLT). When we focus instead on stationary states of typical complex systems (e.g., classical long-range Hamiltonian systems), both the CLT and LDT need to be generalized. Specifically, when the N->infinity attractor in the space of distributions is a Q-Gaussian related to a Q-generalized CLT (Q=1 recovers Gaussian attractors), we expect the LDT probability distribution to approach a q-exponential (where q=f(Q) with f(1)=1, thus recovering the standard LDT exponential distribution) with an argument proportional to N, consistently with thermodynamics. We numerically verify this conjectural scenario for the standard map, the coherent noise model for biological extinctions and earthquakes, the Ehrenfest dog-flea model, and the random-walk avalanches.