"simple" and "complex" may mean very different things in this context ; it could refer to the simplicity/complexity in usage or refer to the capacity of the classifier to distinguish between patterns
in this last acception, you might want to learn more about the "Vapnik-Chervonenkis dimension", which is a measure of such capacity
http://en.wikipedia.org/wiki/VC_dimension
and maybe go further on such topic with the "fat shattering dimension", nicely introduced here with its implications on PAC learnability
"simple" and "complex" may mean very different things in this context ; it could refer to the simplicity/complexity in usage or refer to the capacity of the classifier to distinguish between patterns
in this last acception, you might want to learn more about the "Vapnik-Chervonenkis dimension", which is a measure of such capacity
http://en.wikipedia.org/wiki/VC_dimension
and maybe go further on such topic with the "fat shattering dimension", nicely introduced here with its implications on PAC learnability
To me, "simple" means "inflexible", such as several linear classifiers, and "complex" means "flexible", which are classifiers with several parameters and non-linear boundaries (neural networks are probably the most extreme example).
If you have just a few samples, go for a simple classifier, if you have a lot of data, you can try to fit a more complex one.
Dear colleague, if we have a few samples, our work in data analysis and classification is more difficult than a moderate data set. because we don't have enough data to robust prediction. A big data also has his difficulties. I think in all data set, you can choose different models to get the best classifier, but I cannot establish a good relationship between the size of samples and type of classifier.
for your second question, you can work with ensemble classifier (based on data diversity methods) or fusion based classifier as a flexible methods and Decision Tree, KNN, logistic regression and Bayesian models as a regular models.
I agree to the previous posts, I just want to add that if you want to test different classifiers, from simple to complex, WEKA isa very flexible and well established tool for exploring the functionality of classifiers and the potential of your database: