Let $X$ be a subset of $S_n$. I suppose that the size of $X$ is small compared to the order of $S_n$. In order to quickly check whether $X$ generates $S_n$ I would do the following: For $k=1,2,3\dots$ check whether the group generated by $X$ is $k$-fold transitive. That is a cheap test: Let $\Gamma$ be the graph whose vertices are the $k$-tuples of distinct elements from $\{1,2,\dots,n\}$. Connect two vertices by an edge if an element from $X$ moves one vertex to the other one. Then the group generated by $X$ is $k$-transitive if and only if $\Gamma$ is connected, which is algorithmically easy and cheap to test.
If $X$ passes the test up to $k=6$, then you know that the generated group is $A_n$ or $S_n$, because there are no other $6$-transitive groups. Deciding between these two cases is a matter of checking the signum of the elements from $X$.
In most degrees $n$, there are no $2$-transitive groups besides $A_n$ or $S_n$, so of course you can stop with $k=2$.
Remark 1 (addressing Derek Holt's comment): Indeed, the number of $6$-tuples gets unmanageably large quickly. Instead of $k$-tuples, one can work with $k$-sets. By Kantor's 1972 paper on $k$-homogeneous groups, a $k$-homogeneous group where $k\ge5$ is $k$-transitive. So except for $n=24$ we have to look at $5$-sets at worst. Of course, certainly there are much more efficient methods available.
Remark 2 (addressing Denis Chaperon de Lauzières' comment): Right, while the algorithm is cheap, the proof of its correctness isn't. The OP didn't tell whether he wants to check many small degree cases (say $n\le30$), or some high degree cases. In the former case, one of course does not need the classification of the finite simple groups in order to classify the highly transitive permutation groups.