Para empezar, solo existen fórmulas para resolver las raíces de polinomios hasta grado 4. Hay toda una teoría sobre ello que demuestra la imposibilidad de que haya una fórmula general para ecuaciones de grado 5 o superior.
Segundo, en la práctica el 99,999% del mundo e incluso más solo manejará hasta la fórmula de de segundo grado. La de grado 3 la usan muy pocos y la de grado 4 solo si se programa en un ordenador.
Luego para resolver polinomios de grado 3 o superior lo que más se usa son las fórmulas de aproximación de raíces como el método de Newton-Raphson o incluso el poco convergente método de bisección.
Ah, lo de Ruffini o métodos para calcular raíces racionales es anecdótico, solo si el polinomio está preparado tiene respuestas enteras o racionales y puedes malgastar tu vida intentando resolver un polinomio que no tiene raíces racionales.
Nunca me he planteado la búsqueda de raíces complejas de polinomios. Pero imagino que si en vez de poner como variable la x pones (x+iy) y efectúas la operación tendrás dos polinomios, uno con números reales y otro con factor i. Las raíces serían las comunes a ambos. Pero lo malo de estos polinomios es que serían de dos variables, que se puede resolver pero se hace muy complicado.
Voy a probar uno de orden 2.
x^2 + x + 1 = 0
(x+iy)^2 + x + iy + 1 = 0
x^2 - y^2 + 2ixy +x + iy + 1 = 0
y de aquí salen dos ecuaciones
1) x^2 - y^2 + x + 1 = 0
2) 2xy + y = 0 ==> (2x+1)y = 0
si tomamos y=0 en en primero volvemos al polinomio primero, no sirve
Si tomamos 2x+1 = 0 tenemos
x = -1/2
y sustituyendo en la primera
1/4 - y^2 -1/2 + 1 = 0
y^2 = 1+1/4-1/2 = 3/4
y = +-sqrt(3) / 2
Luego las respuestas serían
1/2 + i·sqrt(3)/2
1/2 - i·sqrt(3)/2
Pero cuando te metas con grado 4 o más no sé hasta dónde se podrá llegar. Seguramente que habrá métodos mejores hechos a propósito para los complejos, pero no conozco ninguno, esto es lo único que se me ocurrió.