There are a lot of senses of "complicated" that can be invoked for languages. There are two kinds of complexity often applied to sound systems, one being the number of segmental units (often divided into consonants versus vowels), and the other being the degree of sequential unpredictability. An example of the first kind is the Khoisan language Taa (ǃXóõ), which has a lot of consonants and vowels -- around 140, though you can't take such numbers at face value because they are influenced by analysis. Likewise, the Caucasian language Ubykh had a massive inventory of consonants. An example of how analysis affects the count is that Taa has been claimed to have "prevoiced" consonants, but another analysis is that they have clusters of voiced plus voiceless consonant.
Sequential unpredictability gives you languages with "complex" combinations of consonants and vowels. Polish allows things like wstrząs, krnąbrność and W Szczebrzeszynie chrząszcz brzmi w trzcinie. In languages with really simple syllable structure, you know that what follows a consonant is a vowel, and what follows a vowel is a consonant; in English you know that what precedes p,t,k in the syllable is s. Georgian has some odd onset clusters such as bg, known as the harmonic clusters, which either constitute examples of "complexity" in diverging from the syllable architype CVCVCV... or which constitute complexity in being additional complex consonants (analogous to "prevoiced" consonants in Taa).
There is a third sense of "complex" not implied by your question (which seems to take the word to be a given, rather than the product of a computation), which is the complexity of computing a given form. Classical Arabic is a good example of that kind of complexity, because the system of rules for deriving a given form (e.g. 1 pl. imperfective jussive 1st measure of the root /wḍʕ/) are complex – there are many rules. The complexity of Japanese writing arises not just from having a lot of graphic primitives, but also from the rules for using graphemes.