Примеры асимптотического анализа

Question

Здесь я буду давать две функции f (n) и g (n), и моя цель - решить, находится ли f (n) в тэте, омеге, большом о, маленьком о или маленьком омеге. Пожалуйста, предоставьте подробные доказательства, если вы уверены в таких проблемах.

Задача 1: f (n) = (1/2) n ^ 2 - 3n, g (n) = n ^ 2

Задача 2: f (n) = 6n ^ 3, g (n) = n ^ 2

Задача 3: f (n) = 3n + 5, g (n) = n ^ 2

Задача 4: f (n) = n потолок (lg n ^ 2), g (n) = n ^ 2 log n

Задача 5: f (n) = [10 ^ (n + 4) (n)] + 6, g (n) = 10 ^ (n + 3)

Answer 1

Полиномиальные функции просты.Просто сравните самый высокий порядок каждого из них.

1. f (n) равно n ^ 2, а g (n) равно n ^ 2, поэтому f (n) равно тета g (n)
2. f (n) - это n ^ 3, а g (n) - это n ^ 2, поэтому f (n) - это O (g (n))
3. f (n) - это n, а g (n)равно n ^ 2, поэтому f (n) равно W (g (n))

Доказательство будет включать вычисление пределов.