The mathematics needed for analysis of algorithms is usually thought in courses/books on the subject (perhaps assuming knowledge from a basic discrete math course/book).
AI is a big field and you'll have to eventually specialize at some point in your graduate education. Speaking for the more machine learning-related areas:
Probability and statistics is a must. More advanced books (e.g. Statistical Learning Theory by Vapnik) and research may use phrases terminology relating to measure theory, but it is probably overkill to learn probability and statistics at that level of detail (likely graduate course) unless you're convinced you want to do work in that area (or are very curious). Calculus would be involved here, but you'll get that either way with math or physics majors. Learning something about Bayesian statistics may also prove useful.
Linear algebra is a must. Typically taught as two courses in undergrad; one more concrete (and probably only finite vector spaces) and the other more focused on abstract matters. The first should be sufficient. But going further can be useful, e.g. kernel methods in machine learning deal with transformations to infinite vector spaces (reproducing kernel Hilbert spaces, in particular).
Numerical optimization is very useful. Maybe you don't need a course and can get away with just studying specific methods as you encounter them in your AI studies. I haven't take a course (I got through my work trying different variants of Newton's method or gradient descent), but I always feel like I should know more about the area in order to improve the performance of my learning algorithm implementations. I've started to watch Boyd's Stanford course on convex optimization to understand this area more. Prereqs are calculus and linear algebra (and probability/statistics for data fitting examples). They use a bunch of terminology for analysis, but claim that studying real analysis isn't necessary for their course (but if you do plan on learning measure theory for probability, then you'll have to be studying real analysis to build up to that!).
Anyway, those are my thoughts from what I've experience studying machine learning in graduate school. Obviously experiences will be different in different areas of AI and what projects you end up working on. My graduate work involved kernel methods and Bayesian statistics, so I used all of the above. If you study say, I don't know, fuzzy logic systems, then probably you need to learn different/additional math. I did take enough math courses as an undergrad CS student to get a minor, but don't let that deter you from physics. I think you'll be learning all of the above, maybe except for optimization, in physics. Perhaps not as formally as you would in math, but that's probably okay.