Во время изучения книги Интервью Взломать код я наткнулся на математическую формулу для нотации Big O, описывающую нотацию Big O для конкатенации строк в Java. Многие принципы программирования имеют математическую основу, такую ​​как нотация Big O, методы, двоичные данные и лежащая в основе науки, лежащая в основе работы языков программирования. Эта статья представляет собой руководство для понимания нотации Big O для конкатенации строк в Java. Он содержит отрывки из книги интервью Взломать код (глава 1).

Код для конкатенации строк

Приведенный выше код на Java описывает функцию, которая принимает массив строковых слов (String [] words) в качестве аргумента функции. Блок кода в скобках {} указывает, что мы будем делать с этими словами. Первая часть указывает, что мы создадим переменную с именем предложение, которое содержит строки. Знак «» указывает, что переменная начинается с пустой строки. Цикл for указывает, что мы будем перебирать массив слов (каждое слово называется aw (String w), и оно помещается в переменную предложения, добавляя его к предложению пустой строки с помощью + w (предложение = предложение + w). Как только цикл завершится прохождением массива, он вернет предложение (часть кода возврата) со всеми словами. В книге интервью Cracking the Code Гейл описывает процесс того, как каждая строка соединены.

Для тех, кто не знаком с Java, строки считаются неизменяемыми типами данных. Хорошую статью о том, что это означает, можно найти здесь. Когда мы объединяем строку, создается копия фактической строки, и каждый символ строки копируется. Если посмотреть на нотацию Big O, описывающую наихудший сценарий для времени выполнения этого кода, Big O описывается как O (xn²). Если вы не знакомы с нотацией Big O, отличную статью можно найти здесь. Это та часть, которая меня озадачила, поскольку я не понимал, как x + 2x +… + nx приводит к нотации Big O для O (xn²). Как человек, которому нравится глубоко погружаться в математические принципы программирования, я решил глубоко погрузиться в математику, лежащую в основе этого большого O. Исследование этой большой нотации O привело меня на математический веб-сайт, на котором описывалась последовательность треугольных чисел. Изображения ниже взяты с этого веб-сайта. Треугольная числовая последовательность описывает количество точек в треугольнике.

Мы начинаем с одной точки и продолжаем добавлять ряды, чтобы создать треугольник. В первом треугольнике с двумя рядами всего 3 точки, потому что мы добавили еще две точки во вторую строку. Когда мы переходим к следующему треугольнику, мы добавляем третий ряд с 3 точками, и общее количество точек равно шести. Если присмотреться, можно найти закономерность, относящуюся к подсчету количества точек в треугольнике. Если вы будете работать в обратном направлении, вы увидите, как появляется шаблон для быстрого определения количества точек. Если у вас 4 ряда, вы можете добавить общее количество точек, считая в обратном порядке. 4 + 3 + 2 +1 = 10 точек. Это правило поиска точек применяется к любому предоставленному номеру. Например, если вы хотите найти общее количество точек в треугольнике с основанием 5, вы просто следуете тому же правилу (5 + 4 + 3 + 2 +1) = 15 точек. Давайте углубимся еще глубже и выясним математическую формулу, вычисляющую количество точек для любого заданного числа, например 5, 4 или 1000000.

N представляет количество точек, с которых мы начинаем (зеленые точки). Мы удваиваем точки новыми точками (желтыми точками), чтобы получился прямоугольник. n становится длиной прямоугольника, а ширина всегда будет n +1. Например, если n равно 3 (длина), тогда ширина будет равна n +1 или (4). Чтобы найти площадь прямоугольника, мы умножаем n * n +1. Если мы продолжим пример, мы получим площадь 4 * 3 или 12. Однако нас интересуют только зеленые точки, поскольку желтые точки использовались только для определения площади прямоугольника. Чтобы найти только общее количество зеленых точек, разделим n * n +1 на 1/2. Это приводит нас к нахождению общего количества зеленых точек равным 6 для n = 3. Это также согласуется с правилом сумм 3 + 2 +1 или 6. Теперь мы можем использовать это правило для вычисления общего количества точек для любого число по этой формуле. Например, если n было 60, вы можете использовать формулу, чтобы вычислить, что будет 1830 точек.

Эта математическая формула связана с конкатенацией строк, потому что при каждой конкатенации создается копия строки, а сами строки копируются. Мы можем представить себе каждую зеленую точку, представляющую строку. Если мы сложим каждую конкатенацию, то получится x + 2x + 3x, что соответствует формуле последовательности треугольных чисел. В нотации Big O нас интересует размер ввода и то, как функция работает с большими размерами ввода. Для конкатенации строки независимо от размера массива Big O всегда будет следовать этой формуле. Big O смотрит на общее количество операций или шагов в зависимости от размера ввода. Если в массиве был один миллион строк или всего десять, по этой формуле будет следовать Big O. В нотации Big O мы отбрасываем значения более низкого порядка, поэтому n (n +1) / 2 равно (n² + n) / 2 или просто n². Это приводит к конкатенации строк с большим O равным O (n²). В Java, чтобы избежать этой ситуации с конкатенацией строк, вы можете использовать что-то под названием StringBuilder. Статью об этом можно здесь.

Я надеюсь, что эта статья помогла вам понять эту математическую концепцию, когда дело доходит до понимания Big O конкатенации строк. Я настоятельно рекомендую добавить в закладки веб-сайты, перечисленные в этой статье, и купить книгу, чтобы понять вопросы собеседования по кодированию «Взломать книгу собеседований по кодированию». (Нет, я не являюсь спонсором этой книги, мне просто нравится учиться на ней !!)