To study the real time problem of nonlinear Kalman filter in SINS／GPS integrated navigation system, the complexity of three usual deterministic sampling nonlinear Kalman filters (UKF, CDKF and CKF) is analyzed and a selection basis is summarized. Numbers of floating-point operations (flops) of the three algorithms are counted according to unified filtering steps, so the accurate expressions of computing complexity are gotten. And a further derivation of the complexity differences among three algorithms is carried out. The aforementioned algorithms are applied in SINS／GPS tightly coupled navigation. Monte Carlo simulation results indicate that three algorithms have similar precision, UKF has the biggest complexity and the complexity of CKF is lower than that of CDKF when the dimension of system states is larger than measurement, and CDKF can get the lowest complexity in some high-dimensional measurement systems.