How does the Ethereum blockchain handle computationally heavy contracts?

That is, if my understanding is correct, every full node (not necessarily a miner) in the blockchain must run smart contract code and validate the resulting deterministic output as part of validating the blockchain.

I'd imagine that submitting a constant number of computationally heavy smart contracts would result in linearly scaling gas costs with the number of smart contracts, but if these took a particularly long time to run, would every node need to run every contract first before continuing with other validation? Would the linearly scaling gas cost necessarily be reflective of linearly scaling computational time?

Is this necessarily a problem? Or is it solved by simply having gas costs that scale with transaction size (and that run time on the EVM correlates to transaction size)?