关于算法分析/效率的问题

Question

我的老师让我分析我的算法。分配的任务是编写一个程序，该程序将一个数字列表作为用户输入，并查找最长的同号序列，标记该数字，并标记起始索引。这个部分已经完成，但是如果有人对我的代码有任何评论，这些也是受欢迎的。以下是他的指示：

算法分析是确定执行算法所需的时间和空间资源。通常，算法的效率或运行时间表示为一个函数，将输入长度与步骤数(称为时间复杂度)或内存体积(称为空间复杂度)联系起来。然而，算法分析的主要关注点是所需的时间或性能。通常，我们执行以下类型的分析−

·最坏情况−：在n大小的任何实例上采取的最大步骤数。

·最佳情况−：在n大小的任何实例上采取的最小步骤数。

·平均情况(−)：对n大小的任何实例采取的平均步骤数。

我的算法是O(n)，因为程序必须迭代整个列表一次吗？同时循环也会影响算法的效率吗？

import java.util.ArrayList;
import java.util.Scanner;

public class Practice {

    public static void main(String[] args) {
        
        Scanner keyboard = new Scanner(System.in);
        ArrayList<Integer> list = new ArrayList<Integer>();
        String temporaryNumber;

        System.out.println("Enter a list of integers, when done, enter 0:");
        while(true) {
            try {
                int j = 0;
                temporaryNumber = keyboard.next();
                int permNumber = Integer.parseInt(temporaryNumber);
                list.add(permNumber);
                j++;
                System.out.println(list); // Displays list as it's typed, OPTIONAL
                if (permNumber == 0) {
                    break;
                }
                else if (permNumber < 0) {
                    System.out.println("Input must be a positive integer.");
                    list.remove(j);
                }
            }
            catch (NumberFormatException e) {
                System.out.println("Input must be a positive integer.");
            }
        }
        keyboard.close();
                int sequenceCount = 1;
                int highestSequenceCount = 0;
                int longestSeqInteger = 0;
                int startingIndexCount = 0;
        
        for (int i = 1; i < list.size() -1; i++) {
                if (list.get(i) == list.get(i-1)) {
                    sequenceCount++;
                }
                else {
                    
                    if (highestSequenceCount < sequenceCount) {
                        highestSequenceCount = sequenceCount;
                        longestSeqInteger = list.get(i-1);
                        startingIndexCount = i - highestSequenceCount;
                        sequenceCount = 1;
                    }
                    else {
                        sequenceCount = 1;
                }
            }
        }
        System.out.println("The longest same number sequence starts at index " + startingIndexCount + ", with " + 
        highestSequenceCount + " values of " + longestSeqInteger); //temp
    }
}

Answer 1

也会影响算法的效率吗？

您需要考虑程序的所有操作，所以是的，while循环也是如此。while循环迭代所有输入(包括被拒绝的输入和输入终止符)一次。

我的算法是O(n)，因为程序必须迭代整个列表一次吗？

它遍历整个列表两次(见上文)，但一次与两次是一个常数尺度因子的问题，因此它本身并不会对渐近界产生影响。

在得出输入上的迭代数可以在O(n)步骤中完成之前，您需要考虑在每个迭代中执行了多少工作，特别是，这是否是输入大小的函数。这是对每个循环的单独分析。如果每个迭代所做的工作与n无关，则每迭代工作的成本为O(1)，因此n次迭代的成本为n* O(1) = O(n)。

Answer 2

你的while循环

• 从用户那里读取输入，
• 执行一些处理(不仅存储在列表中，而且在特定情况下也删除元素)，
• 使用它执行一些输出。

在“算法”中输入用户使您无法对其性能进行推理，因为您通常衡量的是用户的输入速度，而不是程序效率。我不敢假设人类打字的速度是恒定的。

因此，首先定义哪些是算法的一部分，哪些不是(不包括输入和输出，保留所有的计算)，并在理想情况下将其作为自己的方法。我想，这将是for循环，或多或少。

然后，大O符号讨论了运行时的增加，这取决于“输入大小”，因此定义“输入大小”在上下文中意味着什么--最有道理的是，列表的大小。那就叫n。

O(n)意味着(渐近地)加倍n值会导致运行时间的两倍。你应该能评估一下..。

在算法的上下文中定义n的含义并明智地选择是至关重要的。如果您将n定义为最大的输入数字，您可能会发现这对算法的运行时间没有任何影响，因此您将得到一个O(1)结果--由于定义不清的n没有用。