Блог

У меня есть эта проблема, и я не понимаю, как ответ для квадратичного / логарифмического и экспоненциального порядка равен 40, 15 и 100. Я знаю, что формулы для них — O (n2), O (log (n)), O (2n), но не могу сопоставить ответы с этими формулами. Что такое n в этой задаче? Это размер набора данных (20) или 2? Пожалуйста, дайте мне знать ваши мысли.

n относится к размеру входных данных; в данном случае 10/20. Но важной частью является не фактическое значение n , а соотношение между предыдущим и текущим n (в данном случае удвоение входных данных).

• Если алгоритм равен O (1), удвоение размера входных данных не меняет результат. (10 => 10)
• Если алгоритм равен O (n), удвоение входных данных удваивает выходные данные. (10 => 20)
• Если алгоритм равен O (n ^ 2), удвоение входных данных в четыре раза увеличивает выходные данные. (10 => 40)
• Если алгоритм равен O(log(n)), удвоение входных данных умножает выходные данные на log(2). (10 => 15)
• Если алгоритм равен O (k ^ n), удвоение входных данных равносильно повышению выходных данных до 2-й степени. (10 => 100).