performance of new wallet address I study bitcoin and don't exactly understand that how new wallet generate?
The documentation write below sentence:
"For generate new wallet, first search that there is no such wallet"
How we can found that the new wallet didn't generate before?
What is complexity of search?
I study bitcoin and don't exactly understand that how new wallet
  generate?


I think you mean address, not wallet. A wallet is a software application that manages your addresses, and let's you view/spend the Bitcoin associated with them.

Address
A Bitcoin Address is a shortened form of Bitcoin script that locks the funds associated to it. In order to spend the funds, you must provide the necessary input to the script so that it equates to true when the script is executed by nodes on the Bitcoin network. This usually includes a signature of the transaction by the private key associated to the address. Here's an example of a Pay-to-Public-Key Hash (P2PKH) address:

P2PKH
16JrGhLx5bcBSA34kew9V6Mufa4aXhFe9X

Steps to generate the address:


Generate a random 32 byte private key. For example (do not use this): a966eb6058f8ec9f47074a2faadd3dab42e2c60ed05bc34d39d6c0e1d32b8bdf
Calculate it's corresponding public key using secp256k1 elliptic curve
023cba1f4d12d1ce0bced725373769b2262c6daa97be6a0588cfec8ce1a5f0bd09
Calculate the hash = RIPEMD160(SHA256(public-key)): 3a38d44d6a0c8d0bb84e0232cc632b7e48c72e0e
Encode Base58Check(hash): 16JrGhLx5bcBSA34kew9V6Mufa4aXhFe9X


See How to Generate a Bitcoin Address


  How we can found that the new wallet didn't generate before? What is
  complexity of search?


You want to make sure you don't use a private key that someone else might have. There is no way to search all the addresses that might be known because only addresses that have received coins are on the blockchain. Also, many addresses can be derived from the same key pair using different scripts, so you can't be sure you don't have a duplicate just by checking the address.

Since a private key can be nearly any 32 byte number, there are on the order of 10^70 possibilities. You will never have a collision with another key as long as you choose a sufficiently random source for key generation. This is the most important thing to remember. For example, don't use a Brainwallet or any other low entropy source to generate a private key because it makes it easier for someone to guess.