Что такое Big O функции

#javascript #arrays #data-structures

#javascript #массивы #структуры данных

Вопрос:

В настоящее время я изучаю структуры данных и алгоритмы. Я хочу знать, как вычислить сложность пространства и Big O функции. Я написал программу, которая поддерживает первый алфавит каждого индекса массива. Пожалуйста, предложите мне лучший способ сделать это.

 function capitalizeFirst(arr){
    let result = [];
    function helper(array) {
        if (array.length === 0) return;
        let upperCassed = array[0][0].toUpperCase();
        array[0].split(array[0][0])
        array[0] = array[0].split(array[0][0])
        array[0][0] = upperCassed
        result.push(array[0].join(''));
        helper(array.splice(1));
    }


    helper(arr);
    return resu<
}
console.log(capitalizeFirst(['banana', 'orange', 'mango']));

// ['banana', 'orange', 'mango']
// ['Banana', 'Orange', 'Mango']

1. Я думаю, что у этого есть O (1), поскольку он никогда не зацикливается и обращается только к первому элементу.

2. @evolutionxbox за исключением того, что он рекурсивен по всему массиву. Thereofre должно быть O(n) (я думаю!)

3. @Jamiec хорошее место. Я не заметил вызова после нажатия результата.

4. Это O (n), поскольку оно касается каждого элемента и каждого элемента только один раз. И операция для каждого элемента равна O (1), поэтому в целом требуется O (n)

5. Я понял суть. Большое спасибо @evolutionxbox

Ответ №1:

Существует несколько способов решения этого вопроса. Вы можете использовать функцию со стрелкой или функцию javascript. Ниже приведено одно из возможных решений:

 function capitalizeFirstLetter(strArr) {
  strArr.forEach(function (item, index) {
   console.log(item.charAt(0).toUpperCase()   item.slice(1));
  });
}

capitalizeFirstLetter(['banana','mango']);

Что касается сложности пространства, это максимальное пространство памяти, требуемое алгоритмом, и в этом случае мы не используем никакого дополнительного пространства. Следовательно, это O (1) .

Для получения более подробной информации о сложности времени и пространства вы можете обратиться: https://www.hackerearth.com/practice/basic-programming/complexity-analysis/time-and-space-complexity/tutorial/

1. Большое спасибо :). Я пытаюсь стать лучше в программировании.

2. Возможно, вы правы в отношении сложности пространства (я не уверен, TBH), но обычно нас интересует временная сложность.

3. @Jamiec Вы правы. В большинстве случаев учитывается временная сложность. В качестве вопроса, специально заданного для сложности пространства для функции, я выделил только это. Временная сложность для этого будет O (n).

Ответ №2:

Ваш метод работает, но для вычисления Big O я думаю, что он довольно сложный. Он имеет тенденцию скрывать тот факт, что он просто перебирает массив один раз, что сделало бы это O(n) .

Более простой способ — делать именно то, что запрашивает требование, и только это — перебирать массив с заглавной буквы первого символа строки

 function capitalizeFirst(arr){
    for(var i=0;i<arr.length;i  ){
      arr[i] = arr[i][0].toUpperCase()   arr[i].substring(1);
    }
    return arr;
}
console.log(capitalizeFirst(['banana', 'orange', 'mango']));

// ['banana', 'orange', 'mango']
// ['Banana', 'Orange', 'Mango']

Конечно, есть много способов написать вышеупомянутое, но простой цикл с 2 простыми строковыми методами, вероятно, самый простой. Из этого примера ясно, что это O(n) для цикла плюс O(1) для каждой строковой операции — результат остается O(n) неизменным .