Привет, я изучал и пытался научиться проверять временную сложность некоторых алгоритмов.
Я видел это видео, которое было очень полезным.
При этом я удивился и начал пытаться отработать случай Уорста и средний случай некоторых алгоритмов.
Программа № 1: это калькулятор, который рассчитывает в формате RPN.
function evaluate() {
var input = prompt("Please enter your input string\n\nExamples of input strings:\n\n\t1. 10 4 5 + *\n\t2. 10 4 5 + * 2 +\n\t3. 10 8 *");
var values = input.split(" ");
var array = new Array();
for (i in values) {
if (values[i] != "+" && values[i] != "*" && values[i] != "-" && values[i] != "/") {
array.push(parseInt(values[i]));
} else {
var operator = values[i];
var val2 = array.pop();
var val1 = array.pop();
switch (operator) {
case "+":
array.push(eval("val1 + val2"));
break;
case "*":
array.push(eval("val1 * val2"));
break;
case "-":
array.push(eval("val1 - val2"));
break;
case "/":
array.push(eval("val1 / val2"));
break;
}
}
}
if (input == "" || input == null) {
document.writeln("Oops, based on your input we have nothing to calculate for you!");
} else {
document.writeln("Your RPN calculation is: ");
document.writeln(array + " with a starting input string of: " + input);
}
}
Из того, что я понял в этом случае, цикл for в этом случае выполняется постоянное число раз, и это длина массива, затем выполняет инструкцию O (1), следовательно, функция Reduce имеет время Сложность O (1) независимо от размера переданного массива.
Программа № 2: Проверьте, является ли номер простым или нет
function isPrime(num) {
if(num <= 1) return false;
const limit = Math.floor(Math.sqrt(num));
for(let i = 2; i <= limit; i++) {
if(num % i === 0) return false;
}
return true;
}
Поскольку существует один цикл for, и программе необходимо как минимум просмотреть каждое число от 2 до введенного числа, поэтому я думаю, что это O (n).
Пока это то, что я сделал, много размышляя и надеюсь, что они верны. Мой вопрос: есть ли простой способ проверить временную сложность функций, которые я никогда не видел раньше?
П.С. Я думаю, они верны. Пожалуйста, если они не указывают, что и почему.
Спасибо за вашу помощь:)
Обновление
Видимо, я был не прав, и лексикора поправила меня:
# 1 Нет, это не O (1). Предполагая, что один шаг занимает O (1), и у вас есть n шагов, где n - длина массива, временная сложность - O (n).
# 2 Нет, это не O (n). Ваш цикл делает не более sqrt (n) шагов, каждый шаг
O (1), поэтому сложность времени здесь O (sqrt (n)).
Сказав это, я попробовал еще и наткнулся на это в своем учебнике. Это в основном вычисляет приблизительный квадратный корень.
# 3
function sqrt(num) {
guess = num / 3;
do {
lastGuess = guess;
guess = (num / guess + guess) / 2;
while(Math.abs(lastGuess - guess));
return guess; /
Правильно ли я сказать, что это O (n), мои рассуждения таковы, что мы повторяем цикл до тех пор, пока не будет найдено прибл.
# 4 от пользователя благодаря ссылке он вычисляет наибольшее число в массиве. Можно ли с уверенностью сказать, что сложность времени в этом случае составляет O (n), поскольку наибольшее число может быть самым последним, и, следовательно, почему O (n).
Еще раз спасибо