What is meant by - computational complexity $2^x$? Recently Bi-clique Cryptanalysis allowed to obtain following results on full AES ES that claim to have


The first key recovery attack on the full AES-128 with computational
complexity $2^{126.1}$
The first key recovery attack on the full AES-192 with computational complexity $2^{189.7}$
The first key recovery attack on the full AES-256 with computational complexity $2^{254.4}$


What is meant by $2^{126.1}, 2^{189.7}, 2^{254.4}, ...$ and if I happen to create a crypto algorithm on my own (which I know is not a good idea) how can I measure it's strength?
The "many attacks" you're referring to, don't exist.
There are two main attacks on AES. One needs related keys and drops security level signifantly (to about the half of the bits).
You're referring to the other one, the biclique attack on AES.

This is the first attack on the full-rounded version of AES (without related keys) that performs better than brute-force. It weakens AES, but only by a mere 2 bits, which is negligible for practical applications.


  What is meant by $2^{126.1},...$?


These numbers identify the workload the attack requires. You need to perform $2^{126.1}$ "steps" to recover the AES-128 key. One step usually means one call to AES-128. The same applies for the other numbers and AES versions.

EDIT: The following paragraph was obsoleted by an edit to the question. The paragraph after this one now fully applies.


  How can I measure it's [my algorithm's] complexity?


First, I think you're using the wrong term. The complexity of an algorithm usually means the run-time the algorithm needs to be performed. (like ~3.5 cycles for AES with AES-NI). The complexity can aswell mean "how complex is it to describe the algorithm", which is usually measured in lines of code.

But from the context you give I assume you mean "How can I measure my algorithm's strength?".
The strength of an algorithm usually is equal to the complexity of the best known attack. So initially this is brute-force making an 128-bit keyed algorithm having a stength of 128-bit or $2^{128}$. Usually attacks sooner or later lower this boundary, whereas usually the impact on homebrew algorithms is rather severe against the moderate advances in the cryptanalysis against AES.