a certeza que ou a certeza de que?

A forma mais correta é a certeza de que:

      – Ter a certeza de que aconteceu alguma coisa.

Expressões como ter a noção, ter a ideia, ter a certeza, etc. requerem a preposição de, como se pode verificar nos casos em que as expressões não são seguidas de uma outra oração mas antes de um nome, em que é impossível retirar a preposição de:

      – Tenho a certeza de muita coisa.