It is useless considering the algebraic closure of the base field $K$. Indeed, to calculate the $A$'s eigenvalues, using standard numeric methods, is a bad idea because (in general) we only get approximations of them.
Assume, for example, that $A\in M_n(\mathbb{Z})$ ($\mathbb{Z}$ is not even a field). We are led to show that
i) or $\det(xI-A)=x^n$. The calculation can be done (using an elaborate software) in $O(n^3)$ operations. Yet, when $n$ is large, the coefficients may be very large; in binary operations, the complexity can be reduced (via a complicated software) to $(n^{3.2}\log(max(|a_{i,j}|)))^{1+o(1)}$, cf.
https://perso.ens-lyon.fr/gilles.villard/BIBLIOGRAPHIE/PDF/KaVi04.pdf
ii) Either $A^k=0$ where $k\geq n$; we calculate $A^n$ with the binary method $A^2,A^4,\cdots$. We calculate $O(\log n)$ products, that is, using $O(n^3\log n)$ operations. As in i), the entries may be very large; then, in elemetary operations, the complexity is at least in $O(n^4\log n)$.