Какова пространственная сложность этой функции?
Я пытаюсь изучить концепцию пространственно-временной сложности. У меня есть простая функция, которая сравнивает два массива и проверяет, имеет ли второй из них квадратные значения, соответствующие первому. Я лучше понимаю временную сложность и считаю, что для этого примера это будет O(n). Однако для пространства я смущен, если бы это было O(1), поскольку мы всегда устанавливаем логическую переменную (работает) и i внутри цикла, или мы должны учитывать входные данные, которые могут быть разных размеров? Спасибо
let checkSquared = (arr, arr2) => {
let works = true;
works = arr.length === arr2.length
for (let i = 0; i < arr.length; i++) {
works = arr2[i] === (arr[i] * arr[i])
}
return works;
}
использование памяти вашего кода кажется постоянным независимо от размера ввода. Следовательно, я бы предположил, что это O(1)
@VLAZ для времени, которое имеет смысл, но мы не создаем новые переменные в цикле, так почему пространство должно быть o (n)?
На отдельной заметке arr.length !== arr2.length && (works = false) либо напишите оператор if, либо сделайте works = arr.length !== arr2.length - нет необходимости делать одну строку условного выражения, не помещая туда условный код. То же самое с линией внутри петли for - просто сделайте ее works = arr2[i] !== (arr[i] * arr[i])
@ haim770 хорошо, так что при расчете пространства вы смотрите только на использование памяти внутри функции и не обрабатываете входные данные как переменные?
Ах, извините, я думал, вы имели в виду сложность TIME. Да, сложность пространства O(1), вы не занимаете больше памяти линейным образом или что-то в этом роде. Это всегда одни и те же переменные, независимо от ввода.
@VLAZ этот код внутри () после && является кодом условия. Это в основном тернар, но только с оператором if.
@matt, нас интересует пространство, используемое ваш код. Если он получает указатели на огромные структуры данных в качестве аргументов, это не ваш код выделяет это пространство.
@matt Я знаю, что делает код. Это не нужно - вы без необходимости усложнили чтение. Просто сделайте сравнение, так как задание a == b && c = true такое же, как c = a == b. Последнее короче и понятнее, потому что мы знаем, что вы выполняете назначение с самого начала, нам не нужно читать конец строки, чтобы узнать это, а затем возвращаться к началу, чтобы выяснить когда.
@VLAZ аааа, я понимаю, что вы говорите, да, было бы лучше просто сказать, что работает = arr2[i] === (arr[i] * arr[i]
@vlaz нет, works = (...) не получится
![Безумие обратных вызовов в javascript [JS]](https://i.imgur.com/WsjO6zJb.png)
Ответы 1
Ему передаются два массива по ссылке, так что это всего лишь две ссылки на уже существующие объекты. Внутри он создает логическое значение works, число i и, возможно, выделяет некоторое временное пространство для промежуточных значений.
В общем, О(1).
Хорошо, спасибо, теперь просто, например, если бы вместо этого внутри цикла мы переназначали работы как строку каждый раз, когда она менялась в зависимости от ввода ... это было бы o (n), потому что строка может быть разных размеров правильно?
Это зависит от того, что будет в этой строке. Обычно это будет O(m, n) (где m=arr.length и n=arr2.length).
Вы перебираете массив, поэтому это
O(n)