Usually cryptographic strength is given as the effective strength in bits of a security primitive. This is related to the amount of tries necessary to break a primitive. So for AES-128 the effective strength is about 126 bits. The number of bits is of course directly related to the number of tries required to perform an attack. This is often given as a power of two as well (e.g. $2^{126}$ for above). This of course directly relates to the number of bits. The time it costs for a single try of course depends on the runtime and is usually not considered significant.
For attacks it is often necessary as well to keep some kind of state. In that case the memory requirements are described as well. Often the memory requirements are particular to a specific primitive (e.g. the amount of encrypted blocks to store in memory), but usually those are easily converted to bits or bytes.
If the strength is related to an algorithm then of course the order $\mathcal{O}$ is most often used. If an attack has a specific order $\mathcal{O}$ then filling in the parameters of the function should return an approximation of the amount of tries.
Background
Cryptographic strength can be tricky to calculate and is highly dependent on the known attacks. It very much depends on the use of the primitive within a protocol or setting if attacks are applicable at all. Because of this the cryptographic strength shown is just the cryptographic strength of the primitive within its mathematical context. So that would be 128 bit effective for AES-128 and SHA-256 (because of the birthday paradox).
Even then it may be hard to clearly identify cryptographic strength. For instance for DH there is no clearly defined key size. Both the size of the modulus as well as the size of the subgroup should be taken into account. Key size and cryptographic strength do not have to be directly related (and key size may not be that well defined in the first place).
To get a clear idea about cryptographic strength there are organizations such as NIST and ECRYPT (II) take a look at keylength.com and the documents linked from that site.