Big-O для пока l oop без предопределенного количества итераций - PullRequest
Новая
       109

Big-O для пока l oop без предопределенного количества итераций

0 голосов
/ 08 апреля 2020

Я пытаюсь выяснить, что такое пространственно-временная сложность для функции ниже. Функция проверяет, будут ли квадраты чисел a в конечном итоге равны 0.

Например, 19 => 1^2 + 9^2 = 1 + 81 = 82 => 8^2 + 2^2 = 64 + 4 = 68 => 6^2 + 8^2 = 36+64 = 100 => 1^2 + 0 ^2 +0^2 = 1, и функция остановится и вернет true.

У меня возникли проблемы с рассуждением о том, что Пространственно-временная сложность была бы для этого случая. Я чувствую, что сложность пространства равна O (n), поскольку объект используется для хранения значения поиска, а временная сложность также будет равна O (n), поскольку он имеет функцию сокращения, но я не уверен, что это так. 

var isHappy = function(n) {
if(n === 0){
    return false;
}

let lookup = {};
let curNum = n;

while(!lookup[curNum]){
    lookup[curNum] = 1;
    const numStr = curNum.toString().split("").map(x=>parseInt(x));
    const newNum = numStr.reduce((acc, cur) => acc + cur * cur,0);
    if(newNum === 1){
        return true;
    }
    curNum = newNum;
}
return false;  
};
...