计算该算法的小O。

huangapple 未分类评论62阅读模式
标题翻译

Calculating small O for this algorithm

问题

Shell Sort 算法分析

void shellSort(int array[], int n) {
    for (int gap = n / 2; gap > 0; gap /= 2) {
        for (int i = gap; i < n; i += 1) {
            int temp = array[i];
            int j;
            for (j = i; j >= gap && array[j - gap] > temp; j -= gap) {
                array[j] = array[j - gap];
            }
            array[j] = temp;
        }
    }
}

我仍然很难理解如何计算算法的时间复杂度。尽管我了解如何使用大O分析算法,但我不知道如何开始使用小o进行分析。如果你能帮助我,我将非常感激。

英文翻译

Shell Sort Algorithm Analysis

void shellSort(int array[], int n){
    for (int gap = n/2; gap &gt; 0; gap /= 2){
      for (int i = gap; i &lt; n; i += 1) {
        int temp = array[i];
        int j;
        for (j = i; j &gt;= gap &amp;&amp; array[j - gap] &gt; temp; j -= gap){
          array[j] = array[j - gap];
        }
        array[j] = temp;
      }
    }
  }

I still have difficulty in understanding how to calculate the time complexity of an algorithm. Although, I know a bit how to analyze an algorithm using big O but I don't know where to start with analyzing using small o. If u could help me, I'll greatly appreciate it.

huangapple
  • 本文由 发表于 2020年3月4日 08:33:28
  • 转载请务必保留本文链接:https://java.coder-hub.com/60517487.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定