Eu usei muito as referências deste site. regular-expressions.info e para a pergunta acredito que aqui dá pra dar uma boa idéia do quanto Regex pode pesar para avaliar uma simples string regular-expressions.info/catastrophic.html – Marcos Regis 23/10/15 às 12:54
Você deve lembrar que, indiferente da linguagem/biblioteca, regex são Autômato finito determinístico, que serão compilados e transformadas em uma maquina de estados.
Assim você deve ter em mente que ela analisa letra por letra (simbolo por simbolo), até verificar se a sentença é valida ou não.
Se qualquer um dos estados não for comprido ou nenhum dos próximos estados seja encontrado. A sentença é invalida.
Você gera um estado que aponta para ele mesmo, ou gera um "curto" para não passar por aquele estado (*, {0,).
Um quantificador vai disser quantas vezes aquele estado pode ser valido. Um estado mal planejado com quantificador infinito pode ser catastrófico. .*/.+, Exemplo disso aqui. (Aprendi na pratica)
O que ocorre é que ele simplesmente vai continuar seguindo o máximo que pode ate chegar no final da sentença. Quando ele chega no final, faz o caminho inverso, removendo caracteres e verificando se o próximo estado (2º) é satisfeito, no primeiro caractere que satisfaça o próximo estado (2º) ele continua (para o 3º).
Na maioria das vezes não se nota esses problemas pois trabalhamos com strings pequenas que o computador simplesmente vai e volta tão rápido que é quase imperceptível.
Você também deve ter um mente que se você não especifica de onde ela deve começar, então ela simplesmente vai começar de qualquer lugar. Exemplo aqui.