0

我正在尝试确定我的类中的每个方法和构造函数的复杂性指标(Big-theta 表示法),这些方法和构造函数使用数组和链表作为底层结构创建队列。具体来说,我不确定如何查看并快速确定每个方法或构造函数是 O(k) 还是 O(n)。有人可以解释一下吗?

数组类:

public class UnboundedQueueArray<T> implements UnboundedQueue<T> {

  // elements stored in array
  private T[] elements;
  // the number of elements currently in the queue
  private int numElems;

  // initial length of queue
  private static final int INITIAL_LENGTH = 10;

  /**
   * Constructs the UnboundedQueueArray object.
   */
  @SuppressWarnings("unchecked")
  public UnboundedQueueArray() {
    elements = (T[]) new Object[INITIAL_LENGTH];

    numElems = 0;
  }

  /**
   * This method inserts the specified element, unless the
   * queue is full.
   * 
   * @param o The element to be inserted.
   */
  public void insert(T o) {
    // checks and enlarges capacity if necessary
    ensureExtraCapacity(1);

    elements[numElems] = o;
    numElems++;
  }

  // this helper method ensures there is always extra capacity
  // in the queue to insert elements 
  @SuppressWarnings("unchecked")
  private void ensureExtraCapacity(int extraCapacity) {

    if(numElems + extraCapacity > elements.length) {
      // double old capacity
      int newCapacity = elements.length * 2 + extraCapacity;
      // allocate new array
      T[] newElements = (T[]) new Object[newCapacity];
      // copy contents of old array into new array
      for(int i = 0; i < length(); i++) {
        newElements[i] = elements[i];
      }

      // replace old array with new array
      elements = newElements;
    }

  }

  /**
   * This method returns the element at the front of the
   * queue, unless the queue is empty.
   *
   * @return The element at the front of the queue. 
   * @throws EmptyQueueException If the queue is empty.
   */
  public T front() throws EmptyQueueException {
    if(length() == 0) {
      throw new EmptyQueueException("Queue is empty.");
    }

    return elements[0];
  }

  /**
   * This method retrieves and removes the element at the front
   * of the queue, unless the queue is empty.
   * 
   * @return The element at the front of the queue.
   * @throws EmptyQueueException If the queue is empty.
   */
  public T remove() throws EmptyQueueException {
    if(length() == 0) {
      throw new EmptyQueueException("Queue is empty.");
    }

    // retrieve element at front of queue
    T frontElem = elements[0];

    // shift elements to the left
    for(int i = 1; i < length(); i++) {
      elements[i - 1] = elements[i];
    }

    // "null out" last element
    elements[numElems - 1] = null;
    // decrement number of elements
    numElems--;

    return frontElem;
  }

  /**
   * This method reports whether or not the queue contains
   * element(s).
   * 
   * @return If one or more elements exists or not.
   */
  public boolean hasMember() {
    return (length() > 0);
  }

  /**
   * This method returns the current length of the queue.
   * 
   * @return The length of the queue.
   */
  public int length() {
    return numElems;
  }

  /**
   * This method provides a string representation of the queue.
   * 
   * @return The String representation of the queue.
   */
  public String toString() {
    // for empty queue
    if(length() == 0) {
      String str = "[ " + length() + " : ]";
      return str;
    }

    // fencepost algorithm
    String str = "[ " + length() + " : " + elements[0];

    for(int i = 1; i < length(); i++) {
      str += ", " + elements[i];
    }

    str += " ]";

    return str;

  }

}

链表类:

public class UnboundedQueueLinkedList<T> implements UnboundedQueue<T> {

  // the reference to the first link
  private Link first;
  // the reference to the last link (if it exists)
  private Link last;

  // the number of links in the queue
  private int numLinks;

  // initial length of queue
  private static final int INITIAL_LENGTH = 10;

  /**
   * Constructs the UnboundedQueueLinkedList object.
   */
  @SuppressWarnings("unchecked")
  public UnboundedQueueLinkedList() {
    first = null;
    last = null;

    numLinks = 0;
  }

  /**
   * This method inserts the specified element, unless the
   * queue is full.
   * 
   * @param o The element to be inserted.
   */
  public void insert(T o) {

    Link newLink = new Link(o, null);

    if(first == null) {
      // we are adding the first link
      first = newLink;
    } else {  // there are existing links, so add newLink after old last link
      last.next = newLink;
    }

    // update the last link
    last = newLink;

    // increment the number of links in the queue
    numLinks++;

  }

  /**
   * This method returns the element at the front of the
   * queue, unless the queue is empty.
   *
   * @return The element at the front of the queue. 
   * @throws EmptyQueueException If the queue is empty.
   */
  @SuppressWarnings("unchecked")
  public T front() throws EmptyQueueException {
    if(length() == 0) {
      throw new EmptyQueueException("Queue is empty.");
    }

    T frontElem;
    // get link at front of queue
    Link frontLink = getLinkAtPos(0);
    frontElem = (T) frontLink.item;

    return frontElem;
  }

  // this helper method gets the link at the specified position
  private Link getLinkAtPos(int pos) {
    Link p = first;

    for(int i = 0; i < pos; i++) {
      p = p.next;
    }

    return p;
  }

  /**
   * This method retrieves and removes the element at the front
   * of the queue, unless the queue is empty.
   * 
   * @return The element at the front of the queue.
   * @throws EmptyQueueException If the queue is empty.
   */
  @SuppressWarnings("unchecked")
  public T remove() throws EmptyQueueException {
    if(length() == 0) {
      throw new EmptyQueueException("Queue is empty.");
    }

    T removedElem;
    removedElem = (T) first.item;
    // remove "first" link
    first = first.next;

    // update "last" if necessary
    if(first == null) {
      last = null;
    }

    // decrement the number of links in the queue
    numLinks--;

    return removedElem;
  }

  /**
   * This method reports whether or not the queue contains
   * element(s).
   * 
   * @return If one or more elements exists or not.
   */
  public boolean hasMember() {
    return (length() > 0);
  }

  /**
   * This method returns the current length of the queue.
   * 
   * @return The length of the queue.
   */
  public int length() {
    return numLinks;
  }

  /**
   * This method provides a string representation of the queue.
   * 
   * @return The String representation of the queue.
   */
  public String toString() {
    // for empty queue
    if(length() == 0) {
      String str = "[ " + length() + " : ]";

      return str;
    }

    Link p = first;
    String str = "[ " + length() + " : " + p.item;

    for(int i = 1; i < numLinks; i++) {
      p = p.next;
      str += ", " + p.item;
    }

    str += " ]";

    return str; 
  }

  // this helper class creates the links that structure the list
  class Link<T> {

    // data associated with this link
    public Object item;
    // next link, or null if no next link
    public Link next;

    /**
     * Constructs the Link object.
     * 
     * @param item The data to be associated with this Link object.
     * @param next The next link (or null if no next link exists).
     */
    public Link(Object item, Link next) {
      this.item = item;
      this.next = next;
    }

  }

}

编辑:这是堆栈数组类:

public class UnboundedStackArray<T> implements UnboundedStack<T> {

  // elements stored in array
  private T[] elements;
  // the number of elements currently in the stack
  private int numElems;
  // initial depth of stack
  private static final int INITIAL_DEPTH = 10;

  /**
   * Constructs the UnboundedStackArray object.
   */
  @SuppressWarnings("unchecked")
  public UnboundedStackArray() {
    elements = (T[]) new Object[INITIAL_DEPTH];

    numElems = 0;
  }

  /**
   * This method "pushes" an element onto the top of the stack.
   * 
   * @param o The element to be "pushed" (or added) onto the top
   *          of the stack.
   */
  public void push(T o) {
    // ensure space to add element
    ensureExtraCapacity(1);

    elements[numElems] = o;
    // increment the number of elements in the stack
    numElems++;
  }


  // this helper method ensures there is always extra capacity
  // in the stack to "push" (or add) elements onto top of stack
  @SuppressWarnings("unchecked")
  private void ensureExtraCapacity(int extraCapacity) {

    if(numElems + extraCapacity > elements.length) {
      // double old capacity
      int newCapacity = elements.length * 2 + extraCapacity;
      // allocate new array
      T[] newElements = (T[]) new Object[newCapacity];
      // copy contents of old array into new array
      for(int i = 0; i < depth(); i++) {
        newElements[i] = elements[i];
      }

      // replace old array with new array
      elements = newElements;
    }

  }

  /**
   * This method retrieves the element at the top of the stack,
   * unless the stack is empty.
   * 
   * @return The element at the top of the stack.
   * @throws EmptyStackException If the stack is empty.
   */
  public T top() throws EmptyStackException {
    if(depth() == 0) {
      throw new EmptyStackException("Stack is empty");
    }

    return elements[numElems - 1];
  }

  /**
   * This method retrieves and removes the element at the top of
   * the stack, unless the stack is empty.
   * 
   * @return The element at the top of the stack.
   * @throws EmptyStackException If the stack is empty.
   */
  public T pop() throws EmptyStackException {
    if(depth() == 0) {
      throw new EmptyStackException("Stack is empty");
    }

    // retrieve element at top of stack
    T topElem = elements[numElems - 1];
    // "null out" element at top of stack
    elements[numElems - 1] = null;
    // decrement number of elements
    numElems--;

    return topElem;
  }

  /**
   * This method reports whether or not the stack contains
   * element(s).
   * 
   * @return If one or more elements exists or not.
   */
  public boolean hasMember() {
    return (depth() > 0);
  }

  /**
   * This method returns the current depth (or length) of the stack.
   * 
   * @return The depth of the stack.
   */
  public int depth() {
    return numElems;
  }

  /**
   * This method provides a string representation of the stack.
   * 
   * @return The String representation of the stack.
   */
  public String toString() {
    // for empty stack
    if(depth() == 0) {
      String str = "[ " + depth() + " : ]";
      return str;
    }

    String str = "[ " + depth() + " : " + elements[numElems - 1];

    for(int i = numElems - 2; i >= 0; i--) {
      str += ", " + elements[i];
    }

    str += " ]";

    return str;

  }

}

这是堆栈链表类:

public class UnboundedStackLinkedList<T> implements UnboundedStack<T> {

  // the reference to the first link
  private Link first;
  // the reference to the last link (if it exists)
  private Link last;

  // the number of links in the stack
  private int numLinks;

  // initial length of stack
  private static final int INITIAL_LENGTH = 10;

  /**
   * Constructs the UnboundedStackLinkedList object.
   */
  @SuppressWarnings("unchecked")
  public UnboundedStackLinkedList() {
    first = null;
    last = null;

    numLinks = 0;
  }

  /**
   * This method "pushes" an element onto the top of the stack.
   * 
   * @param o The element to be "pushed" (or added) onto the top
   *          of the stack.
   */
  public void push(T o) {
    Link newLink = new Link(o, null);

    if(first == null) {
      // add the first link
      first = newLink;
    } else {  // there are existing links, so add newLink after old last link
      last.next = newLink;
    }

    // update the last link
    last = newLink;

    // increment the number of links in the queue
    numLinks++;
  }

  /**
   * This method retrieves the element at the top of the stack,
   * unless the stack is empty.
   * 
   * @return The element at the top of the stack.
   * @throws EmptyStackException If the stack is empty.
   */
  @SuppressWarnings("unchecked")
  public T top() throws EmptyStackException {
    if(depth() == 0) {
      throw new EmptyStackException("Stack is empty.");
    }

    T topElem;
    // get link at front of queue
    Link topLink = getLinkAtPos(numLinks - 1);
    topElem = (T) topLink.item;

    return topElem;
  }

  // this helper method gets the link at the specified position
  private Link getLinkAtPos(int pos) {
    Link p = first;

    for(int i = 0; i < pos; i++) {
      p = p.next;
    }

    return p;
  }

  /**
   * This method retrieves and removes the element at the top of
   * the stack, unless the stack is empty.
   * 
   * @return The element at the top of the stack.
   * @throws EmptyStackException If the stack is empty.
   */
  @SuppressWarnings("unchecked")
  public T pop() throws EmptyStackException {
    if(depth() == 0) {
      throw new EmptyStackException("Stack is empty.");
    }

    T removedElem;
    removedElem = (T) last.item;

    Link p = first;
    for(int i = 0; i < depth() - 2; i++) {
      p = p.next;
    }

    //p.next = null;

    last = p;

    // update "last" if necessary
    if(first == null) {
      last = null;
    }

    // decrement the number of links in the queue
    numLinks--;

    return removedElem;
  }

  /**
   * This method reports whether or not the stack contains
   * element(s).
   * 
   * @return If one or more elements exists or not.
   */
  public boolean hasMember() {
    return (depth() > 0);
  }

  /**
   * This method returns the current depth (or length) of the stack.
   * 
   * @return The depth of the stack.
   */
  public int depth() {
    return numLinks;
  }

  /**
   * This method provides a string representation of the stack.
   * 
   * @return The String representation of the stack.
   */
  @SuppressWarnings("unchecked")
  public String toString() {
    // for empty stack
    if(depth() == 0) {
      String str = "[ " + depth() + " : ]";
      return str;
    }

    Link pL = last;
    String str = "[ " + depth() + " : " + pL.item;

    for(int i = numLinks - 2; i >= 0; i--) {
      Link tempLink = getLinkAtPos(i);
      str += ", " + tempLink.item;
    }

    str += " ]";

    return str; 
  }

  // this helper class creates the links that structure the list
  class Link<T> {

    /**
     * Data associated with this link.
     */
    public Object item;

    /**
     * Next link, or null if no next link.
     */
    public Link next;

    /**
     * Constructs the Link object.
     * 
     * @param item The data to be associated with this Link object.
     * @param next The next link (or null if no next link exists).
     */
    public Link(Object item, Link next) {
      this.item = item;
      this.next = next;
    }

  }

}
4

3 回答 3

2

数组类:

UnboundedQueueArray: O(1)
插入: O(1)
ensureExtraCapacity: O(n) (n = 当前长度)

“O(n) 是最坏的情况,否则 O(1)”

前:O(1)
删除:O(n)

“总是 O(n)”

长度:O(1)

优化:

我强烈建议您为此行为使用堆栈,因为它以 O(1) 复杂度处理每个方法。

链接列表:

UnboundedQueueLinkedList: O(1)
insert: O(1)
行为似乎不正确

last.next = newLink;
last = newLink;

getLinkAtPos:O(pos)
删除:O(1)
长度:O(1)

可以进行一些优化。

UnboundedQueueLinkedList.getLinkAtPos
如果将其设为双链表,则可以从末尾开始 if pos > length() / 2。这会将最坏情况的复杂性降低到 O(log(n))。

堆栈数组类:

UnboundedStackArray: O(1)
push: O(1) + ensureExtraCapacity
ensureExtraCapacity: wcs 是 O(n), bcs 是 O(1)
top: O(1)
pop: O(1)
depth: O(1)
toString: O (n)

绝对不会将数组用于堆栈,列表效率更高

堆栈链表:

UnboundedStackLinkedList:O(1)
推送:O(1)

再次,看起来功能不正确

top: O(1) + getLinkAtPos
getLinkAtPos: O(n)
pop: O(n)
depth: O(1)
toString: O($n^2$)

这可能会更有效率。

如果您创建一个堆栈,您只需要跟踪该top项目。每次推送时,顶部项目都会被新项目替换,新项目的next链接项目是旧顶部。每次弹出时,顶部项目都会弹出,并将其引用设置为新顶部。唯一比方法更重要O(1)toString()方法。

于 2013-08-04T20:25:46.763 回答
1

@user2581779:我将尝试解释 O(n) 的含义,但我不会检查您的代码。希望您在自己阅读我的答案后能够回答这个(以及其他相关问题)。

为什么是大 O 符号?

首先,您应该了解为什么使用 O 表示法。例如,您可以在给定的计算机上使用几秒钟的执行时间,对吗?

好吧,这有很多问题:

  • 即使每个程序员/计算机科学家都有相同的计算机来执行,时间也会有所不同(由于许多因素,例如温度)
  • 您必须非常小心地处理您的测试用例。假设您要检查对数组中的元素进行排序的算法。你想排序什么(数字/对象)?您要排序多少个对象?这可能会影响您测量的时间
  • 你只会得到你测试过的具体架构/系统的陈述。

好吧,简单地测量秒不是一个好主意。但是你为什么不测量操作的数量呢?

  • 操作的数量可能很难确定(有多少操作int a = 7 + 3?有多少a += b?您必须考虑编译器优化以及底层汇编器的外观)

理论上,当您增加输入大小时,您总是对算法如何发展更感兴趣。

所以,假设你有一个n元素数组。您希望对这些元素进行排序。算法 A 需要n^2 + 1234操作,算法 B需要n^1.9 + 123123123123123操作。哪一个更好?(请注意,这n只是一个变量。我也可以命名它kwhatever

相当长,算法A会表现得更好。但是一旦 B 变得更好(具有更多元素 n),它将比 A 好得多。

因此,您可以忘记加法常数项。还有关于乘法常数。在实践中,乘法常数可能非常重要,但 Big-O 表示法忽略了这一点。

请注意,您关心最坏的情况。最好的案例同样容易检查,但并不有趣。

平均案例分析很难正确完成。如果您想尝试,请搜索“会计方法”或“汇总方法”。

使用 Big-O 表示法是为了什么?

空间和时间复杂度。对于大多数简单的应用程序,只有时间复杂度很重要。但请注意,您通常可以进行时间/空间权衡。当您存储更多信息时,您的算法可能会更快。

Big-O 表示法仅用于感受函数增长的强度。

数学

正式地:

g : N -> R成为一个函数。

O(g(n)) &:= {f(n) | \exists_{c > 0} \exists_{n_0 > 0} \forall_{n \geq n_0}: f(n) < c *g(n) }

(有关渲染版本,请参见我的网站)

这意味着,当说你的程序在 中是正确的O(n),说它在 中也是正确的O(n^2)。大 Theta 表示法使这更好,但更难以正确确定。

如何获得 Big-O 符号?

对于大多数程序,它非常简单:

  • 首先,定义正在增长的值(例如要排序的元素数量)。这是你的n
  • 然后看看循环。
    • 一个循环n意味着你至少在O(n)(虽然可能更糟)
    • 一个嵌套循环,其中两个变量都从 0..n 循环,这意味着你的 inO(n^2)或更糟
  • 看看递归函数。用Master theorem检验它。
  • 看看你调用的数据结构和函数。对于许多 Java 数据结构,您可以通过搜索获得大 O 时间复杂度
  • 当树平衡时,树数据结构通常有一些东西log(n),因为这是树的高度(但前提是你可以保证它是平衡的!)
  • 您可以通过分析总和来获得时间。因此,当您有两个嵌套循环时,一个来自 0..n 并带有运行变量 i,另一个来自 i..n 执行一个“基本”操作,您将得到sum_{i=0}^n \sum_{j=i}^n 1 = sum_{i=0}^n i = (n^2 + n)/2 + 1. 需要一些练习来确定哪些操作是什么1,哪些是n不同的,但是一旦您以数学方式编写了它们,您就可以使用 Wolfram|Alpha 来简化它们。有关示例,请参阅我关于高斯消除的文章。
于 2013-08-04T21:30:34.400 回答
0

具体来说,我不确定如何查看并快速确定每个方法或构造函数是 O(k) 还是 O(n)。

首先,浏览代码并找到所有只包含 O(1) 代码的方法。这些方法不会有运行 n 次的循环,也不会调用 O(n) 方法。由于这些只是直接运行,因此它们是 O(1),即使它们在循环之外调用许多其他 O(1) 方法。如果该方法在 O(0) 代码中循环 n 次,则该方法为 0(n)。如果它有多个不在循环内的 O(n) 操作,它仍然是 O(n),尽管可能具有更大的 n 系数。如果它有执行 n 次的 O(n) 代码,则为 O(n^2)。

大批

UnboundedQueueArray() 是 O(INITIAL_LENGTH),这是 O(1),因为 INITIAL_LENGTH 是常数。ensureExtraCapacity(int extraCapacity)在扩展内部数组时为 O(n),因为它声明了一个大小为 newCapacity 的数组(必须大于 n)并运行循环 n 次,否则为 O(1)。

插入是事情变得有趣的地方。大约每 n 次调用它,它就会调用 ensureExtraCapacity 作为 O(n) 操作。如果你每 n 次调用一次 O(n) 一次,你平均为 O(n/n) 或 O(1)。但由于你偶尔是 O(n),我们给它一个特殊的名称:摊销常数时间。

front、hasMember 和 length 是 O(1),由于循环,remove 是 O(n),而 toString 只有 O(n),因为我们可以在恒定时间内访问元素。

链表

UnboundedQueueLinkedList (the constructor), insert, front, remove, hasMember,并且length都是 O(1)。getLinkAtPos(int pos)可以说是 O(pos),但我们只称它为 O(n),因为最坏的情况会随着 n 变大而变大。

toString()是 O(n^2),因为它执行 O(n) 操作,getLinkAtPos,n 次。

笔记:

如果您返回到 LinkedList 的 toString() 的原始实现,您可以让它下降到 O(n),因为您避免在循环内调用 getLinkAtPos。

public String toString() {
        // for empty queue
        if(length() == 0) {
          String str = "[ " + length() + " : ]";

          return str;
        }

        Link p = first;
        String str = "[ " + length() + " : " + p.item;

        for(int i = 1; i < numLinks; i++) {
          p = p.next;
          str += ", " + p.item;
        }

        str += " ]";

        return str; 
      }
于 2013-08-04T21:24:45.167 回答