Zuoshen Straight through BAT Algorithm Notes (Basic) — Часть 2

Java

Личный технический блог:www.zhenganwen.top

бинарное дерево

Реализовать предварительный, упорядоченный и последующий обход бинарных деревьев, включая рекурсивные и нерекурсивные методы.

рекурсивный путь

public static class Node{
  int data;
  Node left;
  Node right;
  public Node(int data) {
    this.data = data;
  }
}

public static void preOrderRecursive(Node root) {
  if (root != null) {
    System.out.print(root.data+" ");
    preOrderRecursive(root.left);
    preOrderRecursive(root.right);
  }
}

public static void medOrderRecursive(Node root) {
  if (root != null) {
    medOrderRecursive(root.left);
    System.out.print(root.data+" ");
    medOrderRecursive(root.right);
  }
}

public static void postOrderRecursive(Node root) {
  if (root != null) {
    postOrderRecursive(root.left);
    postOrderRecursive(root.right);
    System.out.print(root.data+" ");
  }
}

public static void main(String[] args) {
  Node root = new Node(1);
  root.left = new Node(2);
  root.right = new Node(3);
  root.left.left = new Node(4);
  root.left.right = new Node(5);
  root.right.left = new Node(6);
  root.right.right = new Node(7);
  preOrderRecursive(root);	//1 2 4 5 3 6 7
  System.out.println();
  medOrderRecursive(root);	//4 2 5 1 6 3 7 
  System.out.println();
  postOrderRecursive(root);	//4 5 2 6 7 3 1 
  System.out.println();
}

Взяв за пример первый обход корня бинарного дерева, можно обнаружить, что рекурсивный метод сначала пытается напечатать значение текущего узла, затем пытается напечатать левое поддерево, а затем пытается напечатать правое поддерево после печати левое поддерево.base caseзаключается в том, чтобы остановить расширение подпроцесса, когда узел пуст. Эта рекурсивная попытка определяется структурой самого бинарного дерева, поскольку любой узел бинарного дерева можно рассматривать как корневой узел бинарного дерева (даже листовой узел можно рассматривать как левое и правое поддерево как пустое бинарное дерево). корень).

Глядя на три рекурсивных метода предварительного заказа, по порядку и после заказа, вы обнаружите, что разница заключается во времени вывода значения текущего узла.Вы обнаружите, что каждый узел будет посещен три раза.: считать один раз при входе в метод, один раз при возврате после завершения рекурсивной обработки левого поддерева и один раз при возврате после завершения рекурсивной обработки правого поддерева. Таким образом, вpreOrderRecursiveПомещение оператора печати в начало метода приводит к обходу в прямом порядке;midOrderRecursive, обход по порядку происходит после того, как оператор печати помещен в рекурсивную обработку chu левого поддерева.

нерекурсивный

обход предварительного заказа

Получив корневой узел дерева, сначала выведите значение узла, а затем по очереди поместите его непустой правый дочерний элемент и непустой левый дочерний элемент в стек. Непустой цикл стека: извлеките узел (корневой узел поддерева) из вершины стека и напечатайте его значение, а затем по очереди поместите его непустой правый дочерний элемент и непустой левый дочерний элемент в стек.

public static void preOrderUnRecur(Node root) {
  if (root == null) {
    return;
  }
  Stack<Node> stack = new Stack<>();
  stack.push(root);
  Node cur;
  while (!stack.empty()) {
    cur = stack.pop();
    System.out.print(cur.data+" ");
    if (cur.right != null) {
      stack.push(cur.right);
    }
    if (cur.left != null) {
      stack.push(cur.left);
    }
  }
  System.out.println();
}

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

Неупорядоченный обход

Для дерева поместите все левые границы дерева в стек,rootНаправление состоит в том, чтобы перейти к левому дочернему элементу, пока левый дочерний элемент не пуст. Когда левый дочерний элемент пуст, верхний узел стека выталкивается (в это время узел является корневым узлом дерева, левое поддерево которого пусто. В соответствии с порядковым обходом узел может быть напечатан напрямую, а затем можно выполнить обход узла по порядку (правое поддерево) напечатать, если правый дочерний элемент узла не пуст (указывая на наличие правильного поддерева), затем поместить его правый дочерний элемент в стек, и этот правый потомок может быть корневым узлом поддерева, поэтому это поддерево Левый край стека выдвигается, затем он возвращается к началу и так далее.

public static void medOrderUnRecur(Node root) {
  if (root == null) {
    return;
  }
  Stack<Node> stack = new Stack<>();
  while (!stack.empty() || root != null) {
    if (root != null) {
      stack.push(root);
      root = root.left;
    } else {
      root = stack.pop();
      System.out.print(root.data+" ");
      root = root.right;
    }
  }
  System.out.println();
}
пост-порядковый обход

Идея 1: Подготовьте два стека, один стек используется для сохранения информации об узле при обходе, а другой стек используется для организации заднего корневого порядка (корневой узел продвигается в стеке, правый потомок продвигается вперед, а левый). ребенок продвигается последним).

public static void postOrderUnRecur1(Node root) {
  if (root == null) {
    return;
  }
  Stack<Node> stack1 = new Stack<>();
  Stack<Node> stack2 = new Stack<>();
  stack1.push(root);
  while (!stack1.empty()) {
    root = stack1.pop();
    if (root.left != null) {
      stack1.push(root.left);
    }
    if (root.right != null) {
      stack1.push(root.right);
    }
    stack2.push(root);
  }
  while (!stack2.empty()) {
    System.out.print(stack2.pop().data + " ");
  }
  System.out.println();
}

Идея 2: Используйте только один стек. с двумя переменнымиhиc,hпредставляет последний напечатанный узел,cПредставляет верхний узел стека. Сначала в стек заталкивается корневой узел, а затем стек непуст и зациклен, пустьcравен верхнему элементу стека (c=stack.peek()) выполняет следующие три ветви:

  1. cБудут ли левые и правые детиhравны, если не равны, указатьcЛевый и правый дочерние элементы не являются последними напечатанными узлами.Поскольку левый и правый дочерние элементы являются корневыми узлами левого и правого поддеревьев, в соответствии с характеристиками обратного обхода корня левое и правое поддеревья не должны быть напечатаны , поэтому левый дочерний элемент помещается в стек (выведите левое поддерево). ).
  2. Ветвь 1 не имеет инструкций по выполнениюcЛевый потомок либо не существует, либо левое поддерево только что было напечатано, либо правое поддерево только что было напечатано. В это время, если это один из первых двух случаев, настала очередь печатать правое поддерево, поэтому, еслиcЕсли правый потомок не пуст, он помещается в стек.
  3. Если первые две ветки не выполняются, значитcВсе левое и правое поддеревья распечатаны, так что вытащите и распечатайтеcузел, обновлениеh.
public static void postOrderUnRecur2(Node root) {
  if (root == null) {
    return;
  }
  Node h = null;  //最近一次打印的结点
  Node c = null;  //代表栈顶结点
  Stack<Node> stack = new Stack<>();
  stack.push(root);
  while (!stack.empty()) {
    c = stack.peek();
    if (c.left != null && c.left != h && c.right != h) {
      stack.push(c.left);
    } else if (c.right != null && c.right != h) {
      stack.push(c.right);
    } else {
      System.out.print(stack.pop().data + " ");
      h = c;
    }
  }
  System.out.println();
}

Найдите узел-преемник узла в двоичном дереве, узел также содержит родительский указатель в дополнение к указателям lleft и right.

Узел-преемник здесь отличается от узла-преемника связанного списка. В бинарном дереве узел-предшественник и узел-последователь делятся в соответствии с порядком обхода двух узлов в бинарном дереве. Например, неупорядоченный обход бинарного дерева2 1 3,Так1Узел-преемник3, предшествующий узел2

Конечно, вы можете перемещаться по двоичному дереву по порядку и помечать его при переходе к узлу, тогда следующий узел, который будет напечатан, будет узлом-преемником узла.

Мы можем предположить, что когда мы подходим к узлу в бинарном дереве, если его правое поддерево не пусто, то его преемник должен быть самым левым узлом в его правом поддереве; если его правый дочерний элемент пуст, то его последующий узел должен быть один. своих узлов-предков, который рассматривается как левый потомок (он существует в левом поддереве узла-предка), в противном случае он не имеет узла-преемника.

Здесь, если его правый дочерний элемент пуст, его сложно анализировать, мы можем использовать указательparent, текущий узелnodeи его родительский узелparentизparent.leftСравните и верните напрямую, если они одинаковыparent,в противном случаеnodeприходитьparentпозиция,parentпродолжайте движение вверх до тех пор, покаparentпока не будет достигнут корневой узелnodeвсе равно не равноparentлевый дочерний элемент , затем возвращаетсяnullУказывает, что данный узел не имеет узлов-преемников.

public class FindSuccessorNode {

    public static class Node{
        int data;
        Node left;
        Node right;
        Node parent;

        public Node(int data) {
            this.data = data;
        }
    }

    public static Node findSuccessorNode(Node node){
        if (node == null) {
            return null;
        }
        if (node.right != null) {
            node = node.right;
            while (node.left != null) {
                node = node.left;
            }
            return node;
        } else {
            Node parent = node.parent;
            while (parent != null && parent.left != node) {
                node = parent;
                parent = parent.parent;
            }
            return parent == null ? null : parent;
        }
    }

    public static void main(String[] args) {
        Node root = new Node(1);
        root.left = new Node(2);
        root.left.parent = root;
        root.left.left = new Node(4);
        root.left.left.parent = root.left;
        root.left.right = new Node(5);
        root.left.right.parent = root.left;
        root.right = new Node(3);
        root.right.parent = root;
        root.right.right = new Node(6);
        root.right.right.parent = root.right;

       if (findSuccessorNode(root.left.right) != null) {
            System.out.println("node5's successor node is:"+findSuccessorNode(root.left.right).data);
        } else {
            System.out.println("node5's successor node doesn't exist");
        }

        if (findSuccessorNode(root.right.right) != null) {
            System.out.println("node6's successor node is:"+findSuccessorNode(root.right.right).data);
        } else {
            System.out.println("node6's successor node doesn't exist");
        }
    }
}

Введение в сериализацию и десериализацию бинарных деревьев

Сериализация

Два момента, на которые следует обратить внимание при сериализации бинарных деревьев, заключаются в следующем:

  1. После сериализации значения узла следует добавить терминатор, указывающий на завершение сериализации узла, например!.
  2. Вы не можете игнорировать наличие пустых узлов, вы можете использовать заполнитель, такой как#Представляет сериализацию пустых узлов.
/**
     * 先根遍历的方式进行序列化
     * @param node  序列化来到了哪个结点
     * @return
     */
public static String serializeByPre(Node node) {
  if (node == null) {
    return "#!";
  }
  //收集以当前结点为根节点的树的序列化信息
  String res = node.data + "!";
  //假设能够获取左子树的序列化结果
  res += serializeByPre(node.left);
  //假设能够获取右子树的序列化结果
  res += serializeByPre(node.right);
  //返回以当前结点为根节点的树的序列化结果
  return res;
}

public static void main(String[] args) {
  Node root = new Node(1);
  root.left = new Node(2);
  root.left.left = new Node(4);
  root.left.right = new Node(5);
  root.right = new Node(3);
  root.right.right = new Node(6);

  System.out.println(serializeByPre(root));
}

реконструкция

Как сериализовать, как десериализовать

public static Node reconstrut(String serializeStr) {
  if (serializeStr != null) {
    String[] datas = serializeStr.split("!");
    if (datas.length > 0) {
      //借助队列保存结点数值
      Queue<String> queue = new LinkedList<>();
      for (String data : datas) {
        queue.offer(data);
      }
      return recon(queue);
    }
  }
  return null;
}

private static Node recon(Queue<String> queue) {
  //依次出队元素重建结点
  String data = queue.poll();
  //重建空结点，也是base case，当要重建的某棵子树为空时直接返回
  if (data.equals("#")) {
    return null;
  }
  //重建头结点
  Node root = new Node(Integer.parseInt(data));
  //重建左右子树
  root.left = recon(queue);
  root.right = recon(queue);
  return root;
}

public static void main(String[] args) {
  Node root = new Node(1);
  root.left = new Node(2);
  root.left.left = new Node(4);
  root.left.right = new Node(5);
  root.right = new Node(3);
  root.right.right = new Node(6);

  String str = serializeByPre(root);
  Node root2 = reconstrut(str);
  System.out.println(serializeByPre(root2));
}

Проверить, является ли дерево сбалансированным бинарным деревом

Определение сбалансированного бинарного дерева: когда высота левого поддерева любого поддерева бинарного дерева и высота правого поддерева не отличаются более чем на 1, бинарное дерево является сбалансированным бинарным деревом.

Согласно определению, чтобы подтвердить, является ли бинарное дерево сбалансированным бинарным деревом, необходимо обойти все узлы. При обходе каждого узла, чтобы узнать, является ли поддерево с узлом в качестве корневого узла сбалансированным двоичным деревом, нам нужно собрать две части информации:

  1. Являются ли левое и правое поддеревья узла сбалансированными бинарными деревьями
  2. Каковы высоты левого и правого поддеревьев и превышает ли разница 1

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

package top.zhenganwen.algorithmdemo.recursive;

/**
 * 判断是否为平衡二叉树
 */
public class IsBalanceBTree {
    public static class Node{
        int data;
        Node left;
        Node right;
        public Node(int data) {
            this.data = data;
        }
    }
    /**
     * 遍历时，来到某个结点需要收集的信息
     * 1、以该结点为根节点的树是否是平衡二叉树
     * 2、该结点的高度
     */
    public static class ReturnData {
        public boolean isBalanced;
        public int height;
        public ReturnData(boolean isBalanced, int height) {
            this.isBalanced = isBalanced;
            this.height = height;
        }
    }

    public static ReturnData isBalancedBinaryTree(Node node){
        if (node == null) {
            return new ReturnData(true, 0);
        }
        ReturnData leftData = isBalancedBinaryTree(node.left);
        if (leftData.isBalanced == false) {
            //只要有一棵子树不是平衡二叉树，则会一路返回false，该树的高度自然不必收集了
            return new ReturnData(false, 0);
        }
        ReturnData rightDta = isBalancedBinaryTree(node.right);
        if (rightDta.isBalanced == false) {
            return new ReturnData(false, 0);
        }
        //返回该层收集的结果
        if (Math.abs(leftData.height - rightDta.height) > 1) {
            return new ReturnData(false, 0);
        }
        //若是平衡二叉树，树高等于左右子树较高的那个加1
        return new ReturnData(true, Math.max(leftData.height, rightDta.height) + 1);
    }

    public static void main(String[] args) {
        Node root = new Node(1);
        root.left = new Node(2);
        root.left.left = new Node(4);
        root.right = new Node(3);
        root.right.right = new Node(5);
        root.right.right.right = new Node(6);
        System.out.println(isBalancedBinaryTree(root).isBalanced);	//false
    }
}

Рекурсия очень полезна, и рекурсивное использование в этом вопросе также является классическим использованием, которое может быть очень рутинным:

  1. Проанализируйте, какие шаги необходимы для решения проблемы (здесь нужно пройти по каждому узлу, чтобы подтвердить, является ли поддерево с каждым узлом в качестве корневого узла сбалансированным двоичным деревом)
  2. Определить рекурсию: совпадает ли родительская проблема с дочерней
  3. Какую информацию собирает подпроцесс
  4. Как эта рекурсия использует информацию, возвращаемую подпроцессом, чтобы получить информацию, возвращаемую этим процессом.
  5. base case

Определить, является ли дерево поисковым бинарным деревом

Определение бинарного дерева поиска: для любого поддерева бинарного дерева значение всех узлов левого поддерева меньше значения корневого узла поддерева, а значение всех узлов правого поддерева больше значения значение поддерева Значение корневого узла и значения любых двух узлов всего дерева различны.

По определению неупорядоченный обход двоичного дерева поиска будет восходящей последовательностью. Следовательно, мы можем использовать нерекурсивный метод обхода бинарных деревьев по порядку для сравнения размера двух соседних узлов при обходе по порядку.Пока существует узел, значение которого меньше, чем его преемник, он не поиск по бинарному дереву.

import java.util.Stack;

/**
 * 判断是否是搜索二叉树
 */
public class IsBST {
    public static class Node {
        int data;
        Node left;
        Node right;

        public Node(int data) {
            this.data = data;
        }
    }

    public static boolean isBST(Node root) {
        if (root == null) {
            return true;
        }
        int preData = Integer.MIN_VALUE;
        Stack<Node> stack = new Stack<>();
        while (root != null || !stack.empty()) {
            if (root != null) {
                stack.push(root);
                root = root.left;
            } else {
                Node node = stack.pop();
                if (node.data < preData) {
                    return false;
                } else {
                    preData = node.data;
                }
                root = node.right;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        Node root = new Node(6);
        root.left = new Node(3);
        root.left.left = new Node(1);
        root.left.right = new Node(4);
        root.right = new Node(8);
        root.right.left = new Node(9);
        root.right.right = new Node(10);

        System.out.println(isBST(root));	//false
    }
}

Проверить, является ли дерево полным бинарным деревом

Согласно определению полного бинарного дерева, если узел в бинарном дереве имеет правого потомка, но не имеет левого потомка, он не должен быть полным бинарным деревом; в противном случае, если узел в бинарном дереве имеет левого потомка, но не имеет правый дочерний элемент, то слой, на котором находится узел, все узлы справа от узла должны быть листовыми узлами, иначе это не полное бинарное дерево.

import java.util.LinkedList;
import java.util.Queue;

/**
 * 判断是否为完全二叉树
 */
public class IsCompleteBTree {
    public static class Node {
        int data;
        Node left;
        Node right;
        public Node(int data) {
            this.data = data;
        }
    }

    public static boolean isCompleteBTree(Node root) {
        if (root == null) {
            return true;
        }
        Queue<Node> queue = new LinkedList<>();
        queue.offer(root);
        boolean leaf = false;
        while (!queue.isEmpty()) {
            Node node = queue.poll();
            //左空右不空
            if (node.left == null && node.right != null) {
                return false;
            }
          	//如果开启了叶子结点阶段，结点不能有左右孩子
            if (leaf &&
                    (node.left != null || node.right != null)) {
                return false;
            }
            //将下一层要遍历的加入到队列中
            if (node.left != null) {
                queue.offer(node.left);
            }
            if (node.right != null) {
                queue.offer(node.right);
            } else {
                //左右均为空，或左不空右空。该结点同层的右侧结点均为叶子结点，开启叶子结点阶段
                leaf = true;
            }

        }
        return true;
    }

    public static void main(String[] args) {
        Node root = new Node(1);
        root.left = new Node(2);
        root.right = new Node(3);
        root.left.right = new Node(4);

        System.out.println(isCompleteBTree(root));//false
    }
}

Зная полное бинарное дерево, нахождение количества узлов требует временной сложности 0 (N)

Если мы пройдем по каждому узлу бинарного дерева, чтобы подсчитать количество узлов, то временная сложность будет равнаO(N^2), мы можем использовать количество узлов в полном бинарном дереве, чтобы быть2^h-1(h — количество уровней дерева), чтобы ускорить этот процесс.

Во-первых, полное бинарное дерево.Если крайний левый узел его левого поддерева находится на последнем уровне дерева, то его правое поддерево должно быть полным бинарным деревом с высотойh-1; в противном случае его левое поддерево должно быть полным бинарным деревом высотойh-2. То есть для решения количества узлов в полном бинарном дереве мы можем разложить процесс решения: 1 корневой узел + полное бинарное дерево (высота h-1 или h-2) + полное бинарное дерево (высота h-1). Количество узлов в первых двух можно получить (1 + 2 ^ уровень -1 = 2 ^ уровень), а последнее становится проблемой нахождения количества узлов в полном двоичном дереве, и можно использовать рекурсию.

/**
 * 求一棵完全二叉树的节点个数
 */
public class CBTNodesNum {
  public static class Node {
    int data;
    Node left;
    Node right;
    public Node(int data) {
      super();
      this.data = data;
    }
  }

  // 获取完全二叉树的高度
  public static int getLevelOfCBT(Node root) {
    if (root == null)
      return 0;
    int level = 0;
    while (root != null) {
      level++;
      root = root.left;
    }
    return level;
  }

  public static int getNodesNum(Node node) {
    //base case
    if (node == null)
      return 0;
    int level = getLevelOfCBT(node);
    if (getLevelOfCBT(node.right) == level - 1) {
      // 左子树满，且高度为 level-1；收集左子树节点数2^(level-1)-1和头节点，对右子树重复此过程
      int leftNodesAndRoot = 1 << (level - 1);
      return getNodesNum(node.right) + leftNodesAndRoot;
    } else {
      // 右子树满，且高度为 level-2；收集右子树节点数2^(level-2)-1和头节点1,对左子树重复此过程
      int rightNodesAndRoot = 1 << (level - 2);
      return getNodesNum(node.left) + rightNodesAndRoot;

    }
  }

  public static void main(String[] args) {
    Node root = new Node(1);
    root.left = new Node(2);
    root.right = new Node(3);
    root.left.left = new Node(4);
    root.left.right = new Node(5);
    root.right.left = new Node(6);
    root.right.right = new Node(7);

    System.out.println(getNodesNum(root));
  }
}

и проверить

и проверитьэто деревоструктура данных, для обработки некоторыхнепересекающийся(Непересекающиеся множества) проблемы слияния и запроса. существует одинАлгоритм объединения-нахождения(union-find algorithm) определяет две операции для этой структуры данных:

  • Найти: определяет, к какому подмножеству принадлежит элемент. Его можно использовать для определения того, принадлежат ли два элемента одному и тому же подмножеству.
  • Объединение: объединяет два подмножества в одно множество.

Реализация структуры Union-Find

Во-первых, объединение поискового множества само по себе является структурой, при его построении нам нужно закинуть в него все данные для работы, изначально каждое из данных становится узлом само по себе, и каждый узел имеет родительский указатель (который изначально указывает на собственное).

Изначально каждый узел в объединении считается подмножеством, и мы можем объединить любые два элемента. Примечательно,union(nodeA,nodeB)не узелnodeAиnodeBобъединены в набор, вместоnodeAгде сбор иnodeBСуществующие коллекции объединяются в новое подмножество:

Итак, какова логика объединения двух наборов? Сначала позвольте мне представитьрепрезентативный узелЭта концепция: найти репрезентативный узел множества, в котором находится узел, — это найти узел, чей родительский указатель в наборе указывает на себя (и когда набор инициализируется, каждый узел является репрезентативным узлом своего собственного набора). Затем объединение двух наборов заключается в том, чтобы указать родительский указатель репрезентативного узла набора с меньшим количеством узлов на репрезентативный узел другого набора:

есть еще одинfindОперация: найти, принадлежат ли два узла одному и тому же множеству. Нам нужно только решить, является ли репрезентативный узел набора, в котором расположены два узла, одним и тем же:

Пример кода:

import java.util.*;

public class UnionFindSet{
	public static class Node{
		//whatever you like to store   int , char , String ..etc
	}
	private Map<Node,Node> fatherMap;
	private Map<Node,Integer> nodesNumMap;

	//give me the all nodes need to save into the UnionFindSet
	public UnionFindSet(List<Node> nodes){
		fatherMap = new HashMap();
		nodesNumMap = new HashMap();
		for(Node node : nodes){
			fatherMap.put(node,node);
			nodesNumMap.put(node,1);
		}
	}

	public void union(Node a,Node b){
		if(a == null || b == null){
			return;
		}
		Node rootOfA = getRoot(a);
		Node rootOfB = getRoot(b);
		if(rootOfA != rootOfB){
			int numOfA = nodesNumMap.get(rootOfA);
			int numOfB = nodesNumMap.get(rootOfB);
			if(numOfA >= numOfB){
				fatherMap.put(rootOfB , rootOfA);
				nodesNumMap.put(rootOfA, numOfA + numOfB);
			}else{
				fatherMap.put(rootOfA , rootOfB);
				nodesNumMap.put(rootOfB, numOfA + numOfB);
			}
		}
	}

	public boolean find(Node a,Node b){
		if(a == null || b == null){
			return false;
		}
		Node rootOfA = getRoot(a);
		Node rootOfB = getRoot(b);
		return rootOfA == rootOfB ? true : false;
	}

	public Node getRoot(Node node){
		if(node == null){
			return null;
		}
		Node father = fatherMap.get(node);
		if(father != node){
			father = fatherMap.get(father);
		}
		fatherMap.put(node, father);
		return father;
	}
	
	public static void main(String[] args){
		Node a = new Node();
		Node b = new Node();
		Node c = new Node();
		Node d = new Node();
		Node e = new Node();
		Node f = new Node();
		Node[] nodes = {a,b,c,d,e,f};

		UnionFindSet set = new UnionFindSet(Arrays.asList(nodes));
		set.union(a, b);
		set.union(c, d);
		set.union(b, e);
		set.union(a, c);
		System.out.println(set.find(d,e));
	}
}

ты найдешьunionиfindБудет процесс нахождения репрезентативного узла множества, в котором находится узел, поэтому я выделил его отдельно вgetRoot, и используйте рекурсию для оптимизации: при поиске репрезентативного узла набора, в котором находится узел, он будет продолжать искать родительский указатель, чтобы указать на свой собственный узел, и, наконец, когда рекурсия вернется, родительский будет использоваться указатель узла, проходящего по пути, вместо этого укажите непосредственно на узел делегата:

Конечно, это сделано для повышения эффективности следующего поиска.

Применение Union Check

Сама структура union-find на самом деле очень проста, но ее применение очень сложно. здесь спроблема островаВ качестве введения, когда матрица довольно велика, очень неэффективно запускать этот обход и заражение на одноядерном процессоре, и для завершения статистики количества островов может использоваться фреймворк параллельных вычислений. То есть матрица может быть разделена на несколько частей, подсчитана одна за другой и, наконец, суммирована. Итак, возникает вопрос:

Количество островов в приведенной выше матрице равно 1, но если разрезать ее по вертикали от середины, количество островов слева равно 1, количество островов справа равно 2, а общее количество равно 3. Как быть с повторяющейся статистикой, вызванной 1 соседней на границе между соседними подматрицами после разрезания? На самом деле эту проблему легко решить, используя функцию поиска по объединению:

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

Жадная стратегия

объединенный наименьший лексикографический порядок

Для заданного массива строк строкового типа найдите такой способ конкатенации, чтобы строка, образованная путем конкатенации всех строк, имела наименьший лексикографический порядок.

Идея многих людей в этом вопросе состоит в том, чтобы отсортировать массивы лексикографически, а затем соединить их от начала до конца, и в результате получится строка с наименьшим лексикографическим порядком среди всех результатов конкатенации. Но легко доказать неправоту, например[ba,b]Результат сортировки[b,ba], результат конкатенацииbba,ноbabлексикографический порядок меньше.

Правильная стратегия заключается в том, что при склейке упорядоченного массива строк от начала до конца следует брать тот, у которого лексикографический порядок меньше среди результатов склейки парной склейки. Доказательство следующее

если заказ.представляет символ сращивания, то предложение здесь таково, еслиstr1.str2 < str2.str2иstr2.str3 < str3.str2, то должно бытьstr1.str3 < str3.str1. Это можно доказать с помощью математической индукции. еслиa~zсоответствует0~25, процесс сравнения лексикографического порядка двух строк на самом деле является процессом сравнения размера двух 26-значных чисел.str1.str2Процесс склейки можно рассматривать как процесс склейки двух шестнадцатеричных чисел.Если две строки разбираются на числаint1иint2, то конкатенация соответствуетint1 * 26^(str2的长度) + int2, то процесс доказательства становится рекурсией двух целочисленных неравенств к другому неравенству.

Золотые слитки и медные пластины

Золотой слиток, разрезанный пополам, стоит столько же меди, сколько и его длина. Например, золотой слиток длиной 20 будет стоить 20 медных пластин, независимо от того, как долго он разрезается пополам. Группа людей хочет разделить весь золотой слиток, как разделить самую медную пластину?

Например, для массива {10, 20, 30}, представляющего в общей сложности трех человек, длина всего слитка золота составляет 10 + 20 + 30 = 60. Слиток золота разделен на три части: 10, 20, и 30. Если вы сначала разделите золотой слиток длиной 60 на 10 и 50, потратьте 60, а затем разделите золотой слиток длиной 50 на 20 и 30 и потратите 50, чтобы потратить в общей сложности 110 медных пластин. Однако, если вы сначала разделите золотой слиток длиной 60 на 30 и 30 и потратите 60, затем разделите золотой слиток длиной 30 на 10 и 20 и потратите 30, чтобы получить в общей сложности 90 медяков.

Введите массив, верните минимальную стоимость разделения.

Жадная стратегия: бросайте элементы данного массива в маленькую корневую кучу и каждый раз извлекайте два элемента (например, 10 и 20) из маленькой корневой кучи, а сумма этих двух элементов (например, 30) получается с помощью определенное деление стоимости этих двух элементов, а затем кинуть эту сумму в корневую кучу. пока в куче корней не останется только один элемент. (Например, после добавления 30 всплывают 30 и 30, на этот раз стоимость 30+30=60, а затем добавляется 60, в куче только один 60, в конце общая стоимость 30 +60-=90)

public stzuoatic int lessMoney(int arr[]){
  if (arr == null || arr.length == 0) {
    return 0;
  }
  //PriorityQueue是Java语言对堆结构的一个实现，默认将按自然顺序的最小元素放在堆顶
  PriorityQueue<Integer> minHeap = new PriorityQueue();
  for (int i : arr) {
    minHeap.add(i);
  }
  int res = 0;
  int curCost = 0;
  while (minHeap.size() > 1) {
    curCost = minHeap.poll() + minHeap.poll();
    res += curCost;
    minHeap.add(curCost);
  }
  return res;
}

public static void main(String[] args) {
  int arr[] = {10, 20, 30};
  System.out.println(lessMoney(arr));
}

IPO

Вход: параметр 1: положительный массив затрат, параметр 2: положительный массив прибыли, параметр 3: положительное число k, параметр 4: положительное число m. Costs[i] представляет собой стоимость (стоимость) проекта i, profits[i] представляет собой деньги (прибыль), которые можно получить после вычета стоимости проекта i после завершения проекта i, k означает, что нельзя запускать параллельно , только в серии Выполняйте не более k проектов m представляет ваш первоначальный капитал.

Объяснение: Каждый раз, когда вы заканчиваете проект, доход, который вы получаете немедленно, может поддержать вас в следующем проекте.

Результат: максимальная сумма денег, которую вы заработали в последний раз.

Жадная стратегия: с помощью двух куч, одна из которых представляет собой небольшую корневую кучу, в которой хранятся затраты на каждый проект, а другая — большую корневую кучу, в которой хранится прибыль от каждого проекта. Во-первых, поместите все проекты в маленькую корневую кучу, а большая корневая стопка пуста.Для существующих средств (основной) в наличии проекты, которые могут быть выполнены (стоимость ниже, чем существующие средства), выбрасываются из малой Корневая куча по очереди и помещается в большую корневую кучу Куча, а затем всплывает верхний элемент большой кучи для завершения и обновляет основную сумму в соответствии с прибылью после завершения. После обновления принципала откройте элементы, которые можно выполнить в малой корневой куче, и добавьте их в большую корневую кучу, а затем откройте верхний элемент в большой корневой куче, чтобы сделать это.Повторяйте эту операцию до определенного момента. основное обновление и два обновления кучи завершены У Dagendui нет проектов для выполнения или количество завершенных проектов достигло k.

import java.util.Comparator;
import java.util.PriorityQueue;

public class IPO {

  public class Project{
    int cost;
    int profit;
    public Project(int cost, int profit) {
      this.cost = cost;
      this.profit = profit;
    }
  }

  public class MinCostHeap implements Comparator<Project> {
    @Override
    public int compare(Project p1, Project p2) {
      return p1.cost-p2.cost; //升序，由此构造的堆将把花费最小项目的放到堆顶
    }
  }

  public class MaxProfitHeap implements Comparator<Project> {
    @Override
    public int compare(Project p1, Project p2) {
      return p2.profit-p1.profit;
    }
  }

  public int findMaximizedCapital(int costs[], int profits[], int k, int m) {
    int res = 0;
    PriorityQueue<Project> minCostHeap = new PriorityQueue<>(new MinCostHeap());
    PriorityQueue<Project> maxProfitHeap = new PriorityQueue<>(new MaxProfitHeap());
    for (int i = 0; i < costs.length; i++) {
      Project project = new Project(costs[i], profits[i]);
      minCostHeap.add(project);
    }
    for (int i = 0; i < k; i++) {
      //unlock project
      while (minCostHeap.peek().cost < m) {
        maxProfitHeap.add(minCostHeap.poll());
      }
      if (maxProfitHeap.isEmpty()) {
        return m;
      }
      m +=  maxProfitHeap.poll().profit;
    }

    return m;
  }

}

Презентация проекта конференц-зала

Некоторые проекты должны занимать конференц-зал для презентаций, а конференц-зал не может вместить презентации двух проектов одновременно. Дайте вам время начала и время окончания каждого проекта (дайте вам массив, который является конкретным проектом), вы можете составить расписание презентаций, а в конференц-зале должно быть больше всего презентаций. Вернитесь к этому самому сеансу презентации.

Жадная стратегия:

1. Проект с самым ранним временем начала будет организован первым. Контрпример: время начала самое раннее, но продолжительность составляет весь день, и другие проекты не могут быть запланированы.

2. Проект с наименьшей продолжительностью будет организован первым. Контрпример: такая договоренность приведет к тому, что все проекты с временем окончания в этот период и временем начала в этот период не смогут быть запланированы.

3. Оптимальная стратегия: проекты, которые заканчиваются первыми, располагаются первыми.

import java.util.Arrays;
import java.util.Comparator;

public class Schedule {

  public class Project {
    int start;
    int end;
  }

  public class MostEarlyEndComparator implements Comparator<Project> {
    @Override
    public int compare(Project p1, Project p2) {
      return p1.end-p2.end;
    }
  }

  public int solution(Project projects[],int currentTime) {
    //sort by the end time
    Arrays.sort(projects, new MostEarlyEndComparator());
    int res = 0;
    for (int i = 0; i < projects.length; i++) {
      if (currentTime <= projects[i].start) {
        res++;
        currentTime = projects[i].end;
      }
    }
    return res;
  }
}

Опыт: Для задач, связанных с жадными стратегиями, хорошо накапливать опыт, и вам не нужно тратить много сил, чтобы доказать это. При решении задач либо найдите сходство, либо дополните стратегии, а затем используйте логарифмы и тестовые примеры для их доказательства.

рекурсия и динамическое программирование

рекурсия грубой силы:

  1. Превратите проблему в подзадачу того же типа в уменьшенном масштабе.
  2. Существует четкий базовый случай, который не требует рекурсии для продолжения.
  3. Существует процесс принятия решений, когда получены результаты подзадач
  4. не записывайте решение каждой подзадачи

динамическое программирование:

  1. от грубой силы рекурсии
  2. Запишите решение каждой подзадачи,избегать двойного счета
  3. Абстрагируйте процесс насильственной рекурсии в выражение состояния
  4. И есть возможность упростить выражение состояния, чтобы сделать его более лаконичным.

П и НП

P означает, что я точно знаю, как считать, и процесс расчета очень ясен, а проблема NP означает, что я не знаю, как считать, но знаю, как попытаться (рекурсия грубой силы).

рекурсия грубой силы

п!проблема

мы знаемn!Определение , можно решить непосредственно по определению:

int getFactorial_1(int n){
  int res=1;
  for(int i = 1 ; i <= n ; n++){
    res*=i;
  }
  return res;
}

Но мы можем думать об этом таким образом, если мы знаем(n-1)!, что проходит(n-1)! * nне выходиn!Пока что? Итак, мы попробовали следующее:

int getFactorial_2(int n){
  if(n=1)
    return 1;
  return getFactorial_2(n-1) * n;
}

n!зависимый от государства(n-1)!,(n-1)!полагаться(n-2)!, так что зависите от него, покаn=1Этот прорыв, а затем возвращение назад, вы обнаружите, что весь процесс восходит к1 * 2 * 3 * …… * (n-1) * nпроцесс расчета.

Проблема с Ханойской башней

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

public class Hanoi {

    public static void process(String source,String target,String auxiliary,int n){
        if (n == 1) {
            System.out.println("move 1 disk from " + source + " to " + target);
            return;
        }
      	//尝试把前n-1个圆盘暂时放到辅助竹竿->子问题
        process(source, auxiliary, target, n - 1);
      	//将底下最大的圆盘移到目标竹竿
        System.out.println("move 1 disk from "+source+" to "+target);
      	//再尝试将辅助竹竿上的圆盘移回到目标竹竿->子问题
        process(auxiliary,target,source,n-1);
    }

    public static void main(String[] args) {
        process("Left", "Right", "Help", 3);
    }
}

Рассчитывается по основной формулеT(N) = T(N-1)+1+T(N-1), временная сложностьO(2^N)

вывести все подпоследовательности строки

Подпоследовательности и подстроки строк имеют разные определения. Подстрока относится к строке, состоящей из любого количества смежных символов в строке, а подпоследовательность может быть строкой, состоящей из любого количества различных символов в строке.

Попробуйте: для начала пусть подпоследовательность будет пустой строкой и передайте ее рекурсивному методу. Сначала приходите к первому символу строки, далее есть два решения: добавить этот символ в подпоследовательность и не добавлять его в подпоследовательность. Эти два решения будут генерировать две разные подпоследовательности, и подбрасывать эти две подпоследовательности в качестве информации, собранной на этом уровне, в подпроцесс.Подпроцесс приходит ко второму символу строки и отвечает на подпоследовательность, отправленную вышестоящим Еще два решения, . , который в конечном итоге исчерпывает все комбинации подпоследовательностей:

/**
	 * 打印字符串的所有子序列-递归方式
	 * @param str	目标字符串
	 * @param index	当前子过程来到了哪个字符的决策上（要还是不要）
	 * @param res	上级扔给本级的子序列
	 */
public static void printAllSubSequences(String str,int index,String res) {
  //base case ： 当本级子过程来到的位置到达串末尾，则直接打印
  if(index == str.length()) {
    System.out.println(res);
    return;
  }
  //决策是否要index位置上的字符
  printAllSubSequences(str, index+1, res+str.charAt(index));
  printAllSubSequences(str, index+1, res);
}

public static void main(String[] args) {
  printAllSubSequences("abc", 0, "");
}

вывести все перестановки строки

/**
	 * 本级任务：将index之后（包括index）位置上的字符和index上的字符交换，将产生的所有结果扔给下一级
	 * @param str
	 * @param index	
	 */
public static void printAllPermutations(char[] chs,int index) {
  //base case
  if(index == chs.length-1) {
    System.out.println(chs);
    return;
  }
  for (int j = index; j < chs.length; j++) {
    swap(chs,index,j);
    printAllPermutations(chs, index+1);
  }
}

public static void swap(char[] chs,int i,int j) {
  char temp = chs[i];
  chs[i] = chs[j];
  chs[j] = temp;
}

public static void main(String[] args) {
  printAllPermutations("abc".toCharArray(), 0);
}

проблема коровьего теленка

Корова рожает корову в год, и новорождённая корова также может рожать корову через год после трёх лет роста, при условии, что она не умрёт. Найдите количество коров через N лет.

Затем, чтобы найти количество коров в n-м году, его можно вычислить в порядке этой формулы, но этоO(N)Временная сложность , существуетO(logN)Алгоритм (обсуждается заранее).

Насильственная рекурсия заменена на динамическое программирование

Зачем менять динамическое программирование? какой смысл?

Динамическое программирование происходит от насильственной рекурсии, которая представляет собой оптимизацию повторяющихся вычислений в насильственной рекурсии Стратегия заключается в обмене пространства на время.

минимальный путь и

Вам дан двумерный массив, каждое число в двумерном массиве положительное число, требуется пройти из левого верхнего угла в правый нижний, и каждый шаг может быть только вправо или вниз. Числа, пройденные по пути, складываются. Возвращает наименьшую сумму пути.

Рекурсивная пробная версия

/**
	 * 从矩阵matrix的(i,j)位置走到右下角元素，返回最小沿途元素和。每个位置只能向右或向下
	 * 
	 * @param matrix
	 * @param i
	 * @param j
	 * @return 最小路径和
	 */
public static int minPathSum(int matrix[][], int i, int j) {
  // 如果(i,j)就是右下角的元素
  if (i == matrix.length - 1 && j == matrix[0].length - 1) {
    return matrix[i][j];
  }
  // 如果(i,j)在右边界上，只能向下走
  if (j == matrix[0].length - 1) {
    return matrix[i][j] + minPathSum(matrix, i + 1, j);
  }
  // 如果(i,j)在下边界上，只能向右走
  if (i == matrix.length - 1) {
    return matrix[i][j] + minPathSum(matrix, i, j + 1);
  }
  // 不是上述三种情况，那么(i,j)就有向下和向右两种决策，取决策结果最小的那个
  int left = minPathSum(matrix, i, j + 1);
  int down = minPathSum(matrix, i + 1, j);
  return matrix[i][j] + Math.min(left,down );
}

public static void main(String[] args) {
  int matrix[][] = { 
    { 9, 1, 0, 1 }, 
    { 4, 8, 1, 0 }, 
    { 1, 4, 2, 3 } 
  };
  System.out.println(minPathSum(matrix, 0, 0)); //14
}

Измените динамическое программирование в соответствии с пробной версией

Недостатком описанной выше рекурсии грубой силы является то, что некоторые подпроцессы повторяются. НапримерminPathSum(matrix,0,1)иminPathSum(matrix,1,0)подпроцессminPathSum(matrix,1,1)состояние (результат выполнения), то в расчетеminPathSum(matrix,0,0)неизбежно приведет кminPathSum(matrix,1,1)повторный счет. Тогда мы можем добиться оптимизации всего процесса, кэшируя результаты вычислений подпроцесса и используя их напрямую, когда это необходимо снова.

Ядро смены динамического программирования от насильственной рекурсии состоит в том, чтобы записать результаты расчета каждого подпроцесса, чтобы достичь цели меняющегося пространства для времени. ТакminPath(int matrix[][],int i,int j)средняя переменнаяiиjРазличные значения приведут кi*jрезультаты, мы сохраняем эти результаты вi*jРазве в таблице не достигается цель динамического программирования?

Наблюдая за приведенным выше кодом, мы видим, что элементы в правом нижнем углу, правой границе и нижней границе не нужно пробовать (существует только один способ перемещения, и нет проблемы с принятием решения), поэтому мы может сначала напрямую вычислить результаты в этих позициях:

Движение элементов на других позициях зависит от минимальной суммы пути соседнего положения справа (i, j + 1) в нижний правый угол и минимальная сумма пути соседнего положения ниже (i + 1, j), чтобы нижний правый угол. Сравните, основываясь на этом, чтобы принять решение идти вправо или налево. Но поскольку мы уже рассчитали результаты на правом и нижнем граничных позициях, не сложно определить результаты на других позициях:

мы начинаем сbase caseВ начале результаты расчета всех подпроцессов меняются местами, двойного расчета нет. НаконецminPathSum(matrix,0,0)Тоже решено.

Это динамическое программирование, и это не то, что вы придумали из воздуха. Сначала попробуем решить эту проблему и напишем рекурсию методом полного перебора. Затем создается соответствующая таблица записей результатов по диапазону изменения переменных в насильственной рекурсии, чтобыbase caseВ результате прорыва, который можно определить непосредственно, окончательно разрешается результат, соответствующий общей ситуации.

Является ли число суммой любого числа в массиве

Дайте вам массив arr и целочисленный AIM. Если вы можете выбрать числа в Arr, вы можете добавить AIM, вернуть TRUE или FALSE.

Идея этой задачи согласуется с идеей решения всех подпоследовательностей строки и исчерпывающим образом перечисляет различные результаты сложения всех произвольных чисел в массиве.

Рекурсивная версия грубой силы

/**
     * 选择任意个arr中的元素相加是否能得到aim
     *
     * @param arr
     * @param aim
     * @param sum 上级扔给我的结果
     * @param i   决策来到了下标为i的元素上
     * @return
     */
public static boolean isSum(int arr[], int aim, int sum,int i) {
  //决策完毕
  if (i == arr.length) {
    return sum == aim;
  }
  //决策来到了arr[i]：加上arr[i]或不加上。将结果扔给下一级
  return isSum(arr, aim, sum + arr[i], i + 1) || isSum(arr, aim, sum, i + 1);
}

public static void main(String[] args) {
  int arr[] = {1, 2, 3};
  System.out.println(isSum(arr, 5, 0, 0));
  System.out.println(isSum(arr, 6, 0, 0));
  System.out.println(isSum(arr, 7, 0, 0));
}

Насильственное динамическое программирование рекурсивных изменений (высокая рутина)

  1. Сначала посмотрите на параметры рекурсивной функции и найдите переменные. здесьarrиaimтолько фиксированная и переменнаяsumиi.

  2. Создайте таблицу для хранения результатов различных подпроцессов, соответствующих диапазону изменений переменных, здесьiДиапазон вариации0~arr.length-1который0~2,иsumДиапазон вариации0~数组元素总和,Сейчас0~6. Поэтому необходимо построить3*7Таблица.

  3. отbase caseДля начала вычислите непосредственно вычисляемые подпроцессы, чтобыisSum(5,0,0)Расчет , например, результат после решения "ли +3" в его подпроцессе может быть определен:

  4. Согласно рекурсивной функцииbase caseВ следующем пробном процессе получаются результаты вычислений других подпроцессов.Здесь мы используемi=1,sum=1Пример вывода:

Какую рекурсию грубой силы можно заменить динамическим программированием

Прочитав приведенные выше примеры, вы обнаружите, что до тех пор, пока вы можете написать пробную версию, изменение динамического программирования является очень рутинным. Но не всякая рекурсия грубой силы может изменить динамическое программирование? Нет, например, в задаче о ханойской башне и проблеме N королев каждый шаг их рекурсии необходим и нет лишнего. Это включает рекурсивные последействия и отсутствие последействий.

С последствиями и без

Отсутствие последействия означает, что для подпроцесса в рекурсии решение вышестоящего не влияет на последующее решение подпроцесса. Например, в задаче о минимальной сумме путей в качестве примера используется следующая матрица:

Для 8 в позиции (1, 1) либо на9->1->8все еще9->4->8прийти к этому8На этом8Расчет суммы минимального пути до правого нижнего угла не меняется. Это не последействие.

Только грубая рекурсия без последствий может изменить динамическое программирование.

хэш

хэш-функция

Энциклопедия:хэш-функция(английский: хэш-функция), также известная какхеш-алгоритм,хэш-функция, это способ создать небольшойномерМетод «отпечатков пальцев». Хэш-функция сжимает сообщение или данные в дайджест, уменьшая объем данных и фиксируя формат данных. Эта функция перемешивает данные в поле ввода и воссоздаетхэш-значение(хэш-значения, хэш-коды, хеш-суммы или хэши) отпечатки пальцев.

Свойства хеш-функций

Входным полем хеш-функции может быть очень большой диапазон, например, любая строка, а выходным полем является фиксированный диапазон (определенное количество битов), предполагая S, и оно имеет следующие свойства:

  1. Типичная хеш-функция имеет бесконечный диапазон входных данных.
  2. Когда одно и то же входное значение передается хэш-функции, возвращаемое значение будет таким же.
  3. Когда в хеш-функцию передаются разные входные значения, возвращаемое значение может совпадать, а может и не совпадать.Конечно, поскольку выходное поле равно S, будут разные входные значения, соответствующие элементу в S ( Эта ситуация называетсяхэш-коллизия).
  4. Наиболее важным свойством является то, что возвращаемые значения для множества различных входных значений равномерно распределяются по S.

Первые три свойства являются основой хэш-функции, а четвертый пункт является ключевым для оценки плюсов и минусов хеш-функции.Чем более равномерно распределяются на S все возвращаемые значения, полученные из разных входных значений, тем лучше хэш-функция, и это равномерное распределение не зависит от регулярности появления входных значений. Например, три входных значения «ааа1», «ааа2» и «ааа3» относительно похожи, но результаты, полученные отличной хэш-функцией, должны сильно отличаться.

Классическая реализация хэш-функции

использованная литература:Введение в хеш-функции

Например, результат хеширования двух строк "test" и "test1" с использованием MD5 выглядит следующим образом (результат хэширования равен 128 битам, а диапазон данных равен0~(2^128)-1, обычно преобразуется в 32 шестнадцатеричных числа для отображения):

test	098f6bcd4621d373cade4e832627b4f6
test1 5a105e8b9d40e1329780d62ea2265d8a

хеш-таблица

Энциклопедия:хеш-таблица(Hash table,Также известен какхеш-таблица),основан наключ(Ключ) и получить прямой доступ к месту хранения памятиструктура данных. То есть он преобразует запрашиваемые данные, вычисляя функцию по значению ключа.картаДоступ к записям из одного места в таблице, что ускоряет поиск. Эта функция отображения называетсяхэш-функция, массив, в котором хранятся записи, называетсяхеш-таблица.

Классическая реализация хеш-таблицы

Хеш-таблица изначально будет иметь размер, например 16, и каждый элемент в таблице будет доступен через индекс массива (0~15). Каждый элемент можно рассматривать как ведро.Когда вы хотите поместить данные в таблицу, ключевое значение сохраняемых данных вычисляется хеш-функцией, а хеш-значение равно модулю 16, а результат соответствует 0 ~ 15. Положите его в ведро, соответствующее индексу.

Затем, когда количество данных превышает 16, неизбежно возникает конфликт хэшей (две части данных помещаются в одно и то же ведро после вычисления хэша).После достижения существующих данных в ведре, таким образом, каждое ведро хранит связанный список. Тогда это классическая структура хеш-таблицы:

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

Расширение хеш-таблицы

Если хеш-таблица равна 16, для размера выборки n (количество данных, которые нужно сохранить), если n мало, то в соответствии с хеш-характеристиками хеш-функции каждое ведро будет разделено на эти n данных, поэтому падение Объем данных для каждого сегмента также невелик, что не влияет на эффективность доступа к хеш-таблице (это определяется длиной связанного списка сегмента, поскольку данные трафика должны быть смежными с таблицей цепочки, во-первых, надо пройти точку хвостового соединения, взять Data надо пройти по цепочке значений ключа сравнения таблиц); но если N велико, то в каждом сегментеN/16фрагментов данных, эффективность доступа становитсяO(N). Следовательно, хеш-таблица нуждается в механизме расширения.Когда количество данных в корзине в таблице превышает пороговое значение (O(1)прибытьO(N)Преобразование, требующее взвешивания алгоритма, требует расширения хеш-таблицы (обычно экспоненциального).

Шаг расширения заключается в создании новой хеш-таблицы большего размера (если размер равен m), извлечении данных из исходной хэш-таблицы, модуле хеш-значения значения ключа m и помещении их в корзину, соответствующую новой таблице. , этот процесс также называетсяrehash.

Если да, то оригиналO(N)это становитсяO(log(m/16,N)), например, увеличить емкость в 5 разO(log(5,N))(основание 5, логарифм N). Когда это основание велико, логарифм N будет сжат очень низко, и суммаO(1)Это очень близко, и в реальной инженерии это в основном рассматривается какO(1)использовать.

Вы могли бы сказатьrehashЭто очень трудоемко и приведет к снижению производительности хеш-таблицы, чего можно избежать на стороне. Например, если множитель увеличивается во время расширения, тоrehashКоличество раз будет очень небольшим, а влияние будет минимальным при сбалансированном использовании всей хеш-таблицы. или можно сделатьОфлайн-расширение, когда емкость необходимо увеличить, исходная хеш-таблица по-прежнему используется пользователем и выполняется в другой памяти.rehash, а затем заменить исходную таблицу новой таблицей после завершения, чтобы пользователь не почувствовал этого.rehashвызвать проблемы.

JVM-реализация хэш-таблицы

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

Фильтр Блума

Черный список небезопасных веб-страниц содержит 10 миллиардов занесенных в черный список веб-страниц, а URL-адрес каждой веб-страницы занимает до 64 байт. Теперь, если вы хотите внедрить систему веб-фильтрации, вы можете определить, находится ли веб-страница в черном списке, по URL-адресу веб-страницы, пожалуйста, спроектируйте систему.

Требования следующие:

  1. Система допускает частоту ошибок суждения менее 1 на 10 000.
  2. Не используйте более 30 ГБ дополнительного пространства.

Если эти 10 миллиардов URL-адресов хранятся в базе данных или хэш-таблице, каждый URL-адрес может быть запрошен, но каждый URL-адрес имеет 64 байта, а число равно 10 миллиардам, поэтому требуется не менее 640 ГБ пространства, что не соответствует требованию 2.

Если интервьюер сталкивается с такими проблемами, как система черного списка веб-страниц, система фильтрации спама, система оценки веб-страниц поисковым роботом и т. д., и видит, что система допускает определенный уровень ошибок, но имеет более строгие требования к пространству, то он Скорее всего, интервьюер хочет, чтобы у него были знания о фильтрах Блума. Фильтр Блума точно представляет набор и может точно определить, входит ли элемент в набор. Обратите внимание, что это только точное представление и точное суждение, насколько оно точное? Все зависит от вашего конкретного дизайна, но сделать это правильно невозможно. Преимущество фильтра Блума в том, что он позволяет достичь высокой степени точности, используя очень мало места. Структура состоит изBurton Howard BloomПредставлен в 1970 году.

Так что же такое фильтр Блума?

Предположим, что имеется длинаmМассив битового типа, то есть каждая позиция массива занимает только один бит Если мы знаем, что каждый бит имеет только два состояния 0 и 1, как показано на рисунке:

Иметь в общей сложностиkХеш-функции, область вывода S этих функций больше или равна m, и эти хэш-функции достаточно хороши и независимы друг от друга (умножьте результат вычисления хеш-функции на 6 и разделите на 7). и исходная функция не зависят друг от друга). Затем для того же входного объекта (при условии, что это строка, обозначенная как URL), результаты, вычисленные k хеш-функциями, также независимы. Могут быть одинаковыми или разными, но независимыми друг от друга. Для каждого вычисленного результата возьмите остаток m (%m), а затем установите соответствующую позицию в 1 в битовом массиве (наше изображение называется затемнением). как показано на рисунке

Обозначим массив битового типа какbitMap. До сих пор пара входных объектовbitMapПроцесс воздействия завершен, т.bitMapНекоторые локации будут затемнены. Далее следуйте этому методу и обработайте все входные объекты (10 миллиардов URL-адресов в черном списке). Каждый объект можетbitMapНекоторые из белых позиций окрашены в черный цвет, и вы также можете встретить позиции, которые были окрашены в черный цвет.Если вы встретите позиции, которые были окрашены в черный цвет, пусть они остаются черными. После обработки всех входных объектов можноbitMapЗначительное количество позиций было затемнено. На данный момент был сгенерирован фильтр Блума, и этот фильтр Блума представляет набор всех предыдущих входных объектов.

Затем на этапе проверки, как проверить, является ли объект предыдущим входным объектом (судя, является ли URL-адрес URL-адресом в черном списке)? Предполагая, что объект представляет собой a, чтобы проверить, является ли он предыдущим входным объектом, вычислить k значений от a до k хеш-функций, а затем взять остаток (%m) k значений и получить значение в [0 ,m-1] k значения для дальнобойного урона. следующий вbitMapПосмотрите, все ли эти места черные. Если один не черный, это означает, что он больше не должен быть в этом наборе. Если они все черные, это означает, что в этом наборе есть a, но это может быть неверно оценено.

Чтобы объяснить более конкретно, если a действительно является входным объектом, то при создании фильтра БлумаbitMapСоответствующие k позиций должны быть затемнены, поэтому на этапе проверки нельзя пропустить a, и это не приведет к неправильной оценке. Что вызовет неправильное суждение, так это то, что a, очевидно, не является входным объектом, но если на этапе создания фильтра Блума слишком много входных объектов, иbitMapслишком мало, это приведет кbitMapПодавляющее большинство местоположений уже черноты. Затем чек, может представлять собой положение, соответствующую k, черные, так что ошибка является входным объектом (I.E., URL черного списка). В терминах Лэймана тип фильтра Bloom ошибок «скорее жертвы трех тысяч, никогда не отпускают».

В конце концов, как создать фильтр Блума это? Просто запомните эти три формулы, чтобы:

  • Для объема входных данных n (здесь 10 миллиардов) и частоты ошибок p (здесь 1 из 10 000) размер фильтра Блума m:m = - (n*lnp)/(ln2*ln2), результат вычисления округляется (в этом вопросе m=19,19n, округляется до 20n, то есть 200 миллиардов бит или 25GB)
  • Требуемое количество k хеш-функций:k = ln2 * m/n = 0.7 * m/n(этот вопросk = 0.7 * 20n/n = 14)
  • Поскольку первые два шага округляются в большую сторону, истинная частота ошибок p фильтра Блума, определяемая первыми двумя шагами, равна:p = (1 - e^(-nk/m))^k

Основной принцип алгоритма хеширования согласованности

тема

Инженеры часто используют кластеры серверов для проектирования и реализации кэширования данных. Ниже приведены общие стратегии:

  1. Будь то добавление, запрос или данные о кораллах, сначала замените идентификатор данных хэш-значением с помощью хеш-функции и запишите его как ключ.
  2. Если в настоящее время имеется N машин, рассчитайтеkey%NЗначение , это значение представляет собой номер машины, которой принадлежат данные, независимо от того, выполняются ли операции добавления, удаления или запроса только на этой машине.

Пожалуйста, проанализируйте возможные проблемы, вызванные этой стратегией кэширования, и предложите улучшенные решения.

Разобрать

Потенциальная проблема со стратегией подчиненного кэша, описанной в заголовке, заключается в том, что если машины будут добавлены или удалены (N изменений), стоимость будет очень высокой, и все данные должны будут пересчитывать хеш-значение на основе идентификатора, и значение хеш-функции будет переоценено до нового.Номер машины по модулю ах-ах-да. Затем выполните массивную миграцию данных.

Чтобы решить эти проблемы, давайте представим последовательный алгоритм хеширования, который является хорошей схемой проектирования кэша данных. Мы предполагаем, что диапазон хеш-значения, преобразованного идентификатором данных с помощью хеш-функции, составляет 2^32, что является цифровым пространством 0~(2^32)-1. Теперь мы можем соединить эти числа голова к хвосту, представьте себе замкнутое кольцо, тогда считается, что идентификатор данных соответствует позиции в кольце после вычисления хеш-значения, как показано на рисунке

Далее представьте, что в таком кольце также находятся три машины. Позиция этих трех машин в кольце определяется идентификатором машины (именем хоста или IP-адресом хоста, который уникален для хоста). Вычисленное хеш-значение равно 2^ 32. Режим соответствует кольцу. Итак, как определить, какой машине принадлежит часть данных? Мы можем найти машину, ближайшую к положению по часовой стрелке в позиции на соответствующем кольце данных, и атрибутировать данные этой машине:

В этом случае, если вы удалитеmachine2узел, вам просто нужноmachine2данные переносятся вmachine3, без необходимости прилагать все усилия для переноса всех ваших данных. При добавлении узла необходимо только перенести данные между новым узлом и узлом перед новым узлом в направлении против часовой стрелки к новому узлу.

Но есть еще две проблемы:

  • Когда машин немного, после того, как машины сопоставляются с кольцом через хэш идентификатора машины, несколько машин могут неравномерно делить кольцо.

    Тогда это приведет к неравномерной нагрузке.

  • При добавлении машин возможно нарушение существующего баланса:

Чтобы решить эту проблему перекоса данных, алгоритм последовательного хеширования вводит механизм виртуального узла, то есть для каждой машины вычисляются несколько хэш-значений с помощью разных хэш-функций, а сервисный узел размещается в нескольких местах, что называется виртуальным узлом. Конкретные практики: например, дляmachine1IP192.168.25.132(или имя машины), рассчитано192.168.25.132-1,192.168.25.132-2,192.168.25.132-3,192.168.25.132-4Значение хеш-функции , а затем соответствует кольцу, и то же самое верно и для других машин.В этом случае количество узлов будет увеличиваться.Согласно характеру хеш-функции, баланс, естественно, станет лучше:

В настоящее время алгоритм позиционирования данных остается неизменным, но есть еще одно сопоставление виртуальных узлов с реальными узлами, такое как таблица поиска на рисунке выше. Когда вычисляется, что часть данных принадлежитm2-1Затем в соответствии с переходом таблицы поиска данные, наконец, будут принадлежать фактическому узлу m1.

Существует множество конкретных реализаций, основанных на принципе последовательного хеширования, в том числе алгоритм Chord, алгоритм KAD и т. д. Если вам интересно, вы можете узнать больше.

RandomPool

Разработайте структуру со следующими тремя функциями:

  • вставка (ключ): добавить определенный ключ в структуру, чтобы он не добавлялся повторно.
  • delete(key): Удалить ключ из структуры.
  • getRandom(): возвращает любой ключ в структуре случайным образом с равной вероятностью.

Требование: временная сложность методов вставки, удаления и getRandom равнаO(1)

Идея: использовать две хэш-таблицы и переменнуюsize, таблица хранитkeyМетка , другая таблица принимает определенную метку в соответствии с меткойkey.sizeИспользуется для записи количества данных в структуре. Присоединяйсяkeyкогда будетsizeкакkeyВ две таблицы добавляются метки; удалитьkey, самая большая этикеткаkeyзаменить его иsize--; случайно выбранныхkeyкогда будетsizeВ качестве меток берутся случайные числа в диапазонеkey.

import java.util.HashMap;

public class RandomPool {
    public int size;
    public HashMap<Object, Integer> keySignMap;
    public HashMap<Integer, Object> signKeyMap;

    public RandomPool() {
        this.size = 0;
        this.keySignMap = new HashMap<>();
        this.signKeyMap = new HashMap<>();
    }

    public void insert(Object key) {
        //不重复添加
        if (keySignMap.containsKey(key)) {
            return;
        }
        keySignMap.put(key, size);
        signKeyMap.put(size, key);
        size++;
    }

    public void delete(Object key) {
        if (keySignMap.containsKey(key)) {
            Object lastKey = signKeyMap.get(--size);
            int deleteSign = keySignMap.get(key);
            keySignMap.put(lastKey, deleteSign);
            signKeyMap.put(deleteSign, lastKey);
            keySignMap.remove(key);
            signKeyMap.remove(lastKey);
        }
    }

    public Object getRandom() {
        if (size > 0) {
            return signKeyMap.get((int) (Math.random() * size));
        }
        return null;
    }

}

Советы

логарифм

Обзор

Иногда, когда мы тестируем написанный нами алгоритм, мы используем некоторые простые данные, которые создаем для тестирования. Однако, когда другие тестируют, они могут вводить большое количество данных, чтобы проверить точность и надежность алгоритма.Если в это время будет ошибка, мы не сможем найти ее из-за огромного количества данных ( какие данные неверны при работе, Алгоритм не работал должным образом). Конечно, мы не можем отлаживать такие большие данные с точками останова и поэтапно анализировать ошибочную точку. В настоящее времялогарифмИнк вышел на сцену,логарифмОн заключается в проверке алгоритма путем случайного создания почти всех возможных коротких выборок в качестве входных выборок алгоритма, чтобы большое количество различных выборок с высокой вероятностью гарантировало точность алгоритма, а когда выборка не проходит тест, короткий образец можно распечатать Проанализируйте причину ошибки.

Использование логарифма

  1. Для алгоритма, который вы хотите протестировать
  2. Алгоритм, реализующий ту же функцию, что и алгоритм, но абсолютно корректный и имеющий плохую сложность
  3. Подготовьте большую случайную выборку коротких
  4. Метод реализации сравнения: для каждой выборки сравнить результаты выполнения алгоритма и алгоритма на втором шаге, чтобы судить о правильности алгоритма.
  5. Если есть ошибка выравнивания образца, распечатайте образец
  6. Когда количество выборок велико, сравнительный тест все еще верен, и можно определить, что алгоритм a верен.

Вариант использования логарифма — тестирование самописной сортировки вставками:

void swap(int *a, int *b){
    int temp = *a;
    *a = *b;
    *b = temp;
}

//1.有一个自写的算法，但不知其健壮性（是否会有特殊情况使程序异常中断甚至崩溃）和正确性
void insertionSort(int arr[], int length){
    if(arr==NULL || length<=1){
        return;
    }
    for (int i = 1; i < length; ++i) {
        for (int j = i - 1; j >= 0 || arr[j] <= arr[j + 1]; j--) {
            if (arr[j] > arr[j + 1]) {
                swap(&arr[j], &arr[j + 1]);
            }
        }
    }
}

//2、实现一个功能相同、绝对正确但复杂度不好的算法（这里摘取大家熟知的冒泡排序）
void bubbleSort(int arr[], int length) {
    for (int i = length-1; i > 0; i--) {
        for (int j = 0; j < i; ++j) {
            if (arr[j] > arr[j + 1]) {
                swap(&arr[j], &arr[j + 1]);
            }
        }
    }
}

//3、实现一个能够产生随机简短样本的方法
void generateSample(int arr[], int length){
    for (int i = 0; i < length; ++i) {
        arr[i] = rand() % 100-rand()%100;//控制元素在-100~100之间，考虑到零正负三种情况
    }
}

//4、实现一个比对测试算法和正确算法运算结果的方法
bool isEqual(int arr1[],int arr2[],int length) {
    if (arr1 != NULL && arr2 != NULL) {
        for (int i = 0; i < length; ++i) {
            if (arr1[i] != arr2[i]) {
                return false;
            }
        }
        return true;
    }
    return false;
}

void travels(int arr[], int length){
    for (int i = 0; i < length; ++i) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

void copy(int source[], int target[],int length){
    for (int i = 0; i < length; ++i) {
        target[i] = source[i];
    }
}

int main(){

    srand(time(NULL));
    int testTimes=10000;       
    //循环产生100000个样本进行测试
    for (int i = 0; i < testTimes; ++i) {
        int length = rand() % 10;   //控制每个样本的长度在10以内，便于出错时分析样本（因为简短）
        int arr[length];
        generateSample(arr, length);

      	//不要改变原始样本，在复制样本上改动
        int arr1[length], arr2[length];
        copy(arr, arr1, length);
        copy(arr, arr2, length);
        bubbleSort(arr1,length);
        insertionSort(arr2, length);

//        travels(arr, length);
//        travels(arr1, length);

      	//5、比对两个算法，只要有一个样本没通过就终止，并打印原始样本
        if (!isEqual(arr1, arr2, length)) {
            printf("test fail!the sample is: ");
            travels(arr, length);
            return 0;
        }
    }
   
  	//6、测试全部通过，该算法大概率上正确
    printf("nice!");
    return 0;
}

распечатать бинарное дерево

Иногда мы не уверены, являются ли какие-либо указатели в двоичном дереве пустыми или неправильными.В это время нам нужно распечатать двоичное дерево с чувством иерархии.Следующее предоставляет такой инструмент. Вы можете повернуть голову на 90 градусов против часовой стрелки, чтобы увидеть отпечаток.vУказывает, что головной узел узла является ближайшим к узлу в левом нижнем углу,^Указывает, что головной узел узла является ближайшим к узлу в левом верхнем углу.

package top.zhenganwen.algorithmdemo.recursive;

public class PrintBinaryTree {

	public static class Node {
		public int value;
		public Node left;
		public Node right;

		public Node(int data) {
			this.value = data;
		}
	}

	public static void printTree(Node head) {
		System.out.println("Binary Tree:");
		printInOrder(head, 0, "H", 17);
		System.out.println();
	}

	public static void printInOrder(Node head, int height, String to, int len) {
		if (head == null) {
			return;
		}
		printInOrder(head.right, height + 1, "v", len);
		String val = to + head.value + to;
		int lenM = val.length();
		int lenL = (len - lenM) / 2;
		int lenR = len - lenM - lenL;
		val = getSpace(lenL) + val + getSpace(lenR);
		System.out.println(getSpace(height * len) + val);
		printInOrder(head.left, height + 1, "^", len);
	}

	public static String getSpace(int num) {
		String space = " ";
		StringBuffer buf = new StringBuffer("");
		for (int i = 0; i < num; i++) {
			buf.append(space);
		}
		return buf.toString();
	}

	public static void main(String[] args) {
		Node head = new Node(1);
		head.left = new Node(-222222222);
		head.right = new Node(3);
		head.left.left = new Node(Integer.MIN_VALUE);
		head.right.left = new Node(55555555);
		head.right.right = new Node(66);
		head.left.left.right = new Node(777);
		printTree(head);

		head = new Node(1);
		head.left = new Node(2);
		head.right = new Node(3);
		head.left.left = new Node(4);
		head.right.left = new Node(5);
		head.right.right = new Node(6);
		head.left.left.right = new Node(7);
		printTree(head);

		head = new Node(1);
		head.left = new Node(1);
		head.right = new Node(1);
		head.left.left = new Node(1);
		head.right.left = new Node(1);
		head.right.right = new Node(1);
		head.left.left.right = new Node(1);
		printTree(head);

	}

}

Суть рекурсии и Мастер-формула

Суть рекурсии

Суть рекурсии в том, что система проталкивает стек за нас. Сначала давайте рассмотрим пример рекурсивного нахождения факториала:

int fun(int n){
	if(n==0){
    return 1;
	}
  return n*fun(n-1);
}

В классе учителя обычно говорят нам, что рекурсия — это функция, вызывающая сама себя. Но это звучит загадочно. На самом деле, если во время выполнения функции вызываются другие функции, статус выполнения текущей функции (какая строка выполняется, сколько там переменных, каково значение каждой переменной и т. д.) будет сохранен и отправлен в стек (расширенный В более поздней структуре хранения, обычно называемый стеком вызовов функций), он поворачивается для выполнения подпроцесса (другие функции, вызываемые, конечно же, текущей функцией). Если функция снова вызывается в подпроцессе, состояние выполнения подпроцесса перед вызовом также будет сохранено и помещено в стек, а вместо этого будет выполнен подпроцесс подпроцесса... и так далее, пока не появится подпроцесс, который не вызывает функцию и может. поверните и продолжайте выполнять до тех пор, пока функции в стеке вызовов функций не будут выполнены, и весь рекурсивный процесс завершится.

Например, вmainвыполнить вfun(3), рекурсивный процесс выглядит следующим образом:

int main(){
  int i = fun(3);
  printf("%d",i);
  return 0;
}

Много раз, когда мы анализируем рекурсию, нам нравится мысленно моделировать выполнение кода, чтобы отслеживать и восстанавливать весь процесс рекурсивного вызова. Но на самом деле в этом нет необходимости, потому что логика, выполняемая каждыми соседними двумя шагами, одинакова, поэтому нам нужно только проанализировать, как выполняются шаги с первого по второй и где находится конечная точка рекурсии.

Все рекурсивные алгоритмы можно преобразовать в нерекурсивные, потому что мы можем сами запушить стек. Просто рекурсивное письмо более лаконично. В практической инженерии использование рекурсии очень редко, потому что рекурсивное создание подфункций дорого и имеет проблемы с безопасностью (переполнение стека).

Основная формула

Временную сложность алгоритма, включающего рекурсию, иногда трудно проанализировать с поверхности алгоритма, напримерСортировка слиянием. В это время вступает в действие Мастер-формула.Когда временная сложность рекурсивного алгоритма соответствуетT(n)=aT(n/b)+O(n^d)Непосредственную сложность алгоритма можно найти непосредственно в виде:

  • Когда (основание b логарифм a)log(b,a) > d, временная сложностьO(n^log(b,a))
  • когдаlog(b,a) = d, временная сложностьO(n^d * logn)
  • когдаlog(b,a) < d, временная сложностьO(n^d)

в,nразмер выборки,n/b- размер выборки подпроцесса (подразумевается, что размеры выборки подпроцессов должны быть одинаковыми и в сумме составлять общий размер выборки),aколичество выполнений подпроцесса,O(n^d)- временная сложность операции после процесса деления.

В качестве примера сортировки слиянием функциональная онтология сначала объединяет и сортирует левую и правую половины, а размер выборки делится на левую и правую половины.n/2которыйb=2, левое и правое объединяются и сортируются один раз, а количество выполнений подпроцесса равно2которыйa=2, временная сложность операции слиянияO(n+n)=O(n)которыйd=1,следовательноT(n)=2T(n/2)+O(n), соответствуетlog(b,a)=d=1,следовательноВременная сложность сортировки слияниемзаO(n^1*logn)=O(nlogn)

Категории