这个算法是 O(n^2) 还是 O(n)

Question

我有 2 个列表：

事件列表（大小可变，从 1 个元素到无穷大）
EventTypesToFilter 列表（始终 fixed/constant 大小为 1 到最多 3 个元素）

算法需要按事件类型过滤事件。

问题是，算法 1 O(n^2) 和算法 2 O(n)？或者他们都是 O(n)？

我也在代码中标记了代码各个点的O复杂度，请确认它们是否正确p1.1，p1.2，p2.1，p2.2 ?

我根据每个算法的最高复杂度确定每个算法的最终 O 复杂度，我的假设是它们都是 O(n)。

请添加任何进一步的观察，也与可能看起来具有不同 O 复杂性的糖代码有关。

我假设 select 语句不是运行并行或者代码的任何其他部分是运行并行。

有2个主要的列表迭代发生，一个循环迭代固定数量的元素（EventType列表），而另一个循环迭代理论上可以认为是无限的元素（Events列表）。出于这个主要原因，我认为 ALGO1 和 ALGO2 都是 O(n)。如有错误请指正

using System;
using System.Collections.Generic;
using System.Linq;

namespace ConsoleApp2
{
    class Program
    {
        static void Main(string[] args)
        {
            //Algo 1 is O(n) or O(n^2)?
            var resp1 = FilterEventsAlgo1(GetEvents(), GetEventTypesToFilter());
            //Algo 2 is O(n) or O(n^2)?
            var resp2 = FilterEventsAlgo2(GetEvents(), GetEventTypesToFilter());
        }

        static List<EventResponse> FilterEventsAlgo1(List<Event> events, List<EventType> eventTypesToFilter)
        {
            var filteredEvents = new List<EventResponse>();
            //p1.1 is O(n)?
            foreach (Event ev in events)
            {
                //p1.2 is O(1)?
                if (eventTypesToFilter.Any(x => x == ev.EventType))
                {
                    filteredEvents.Add(new EventResponse());
                }
            }
            return filteredEvents;
        }

        static List<EventResponse> FilterEventsAlgo2(List<Event> events, List<EventType> eventTypesToFilter)
        {
            //p2.1 is O(1)?
            events.RemoveAll(x => !eventTypesToFilter.Contains(x.EventType));
            //p2.2 is O(n)?
            var filteredEvents = events.Select(x => new EventResponse()).ToList();

            return filteredEvents;
        }

        static List<Event> GetEvents()
        {
            //... Theretically the number of elements CAN VARY TO A GREATER NUMBER up to infinity
            List<Event> Events = new List<Event> {
                new Event(EventType.Type1),
                new Event(EventType.Type2),
                new Event(EventType.Type3),
                new Event(EventType.Type3),
                new Event(EventType.Type3)
            };
            return Events;
        }

        static List<EventType> GetEventTypesToFilter()
        {
            //... The number of elements in this list is always limited to max 3, can be seen as a constant number of elements
            List<EventType> EventTypesToFilter = new List<EventType> {
                EventType.Type1,
                EventType.Type2,
            };
            return EventTypesToFilter;
        }

    }

    class Event
    {
        public EventType EventType { get; set; }
        public Event(EventType eventType)
        {
            this.EventType = eventType;
        }
    }

    class EventResponse
    {

    }


   
    enum EventType
    {
        Type1,
        Type2,
        Type3
    }
}

Answer 1

它们都是 O(n) 因为 GetEventTypesToFilter 的元素数量是固定的。如果 GetEventTypesToFilter 也随着问题的大小而增长，那么这两种算法都是 O(n^2) 或 O(n * m)。

对于 GetEvents 中的每个事件，您需要做一定数量的工作并循环 GetEvents 一定次数（算法一一次，算法二两次）。

Answer 2

这些算法非常相似，并且都具有相同的复杂度。

如果您想以一种有意义的方式说明复杂性，那么您会说它是 O(events.size() * eventTypesToFilter.size()) 或 O(n * m)，其中n 和 m 是那些尺寸。

如果您真的必须仅根据总输入大小来说明它，那么它将是 O(n²)... 但实际上您不会那样做。如果你说 O(n * m)，那么调用者知道如果他传递给你一个固定大小的事件类型列表，那么他的算法可以是 O(n)，并且他知道调用你的代码的成本是多少会随着 'fixed' 大小的增加而增加。

这个算法是 O(n^2) 还是 O(n)

Is this algorithm O(n^2) or O(n)

c#

algorithm

big-o