询问pandas.apply()结合lambda代码的时间复杂度（大O表示法）

Great question! Let's break this down step by step to clear up the confusion around time complexity here.

First, let's look at your original code:

df1['var1'] = df1['var_ref'].apply(lambda x: True if x in df2.var0.unique() else False) * 1

Breaking down the original code's time complexity #

1. df2.var0.unique(): This operation scans all M rows of df2 to generate a deduplicated numpy array, which takes O(M) time.
2. The apply loop over df1's N rows: For each value x in df1['var_ref'], checking x in df2.var0.unique() is a linear scan of the deduplicated array (since numpy arrays don't support fast lookups). Each check takes O(M) time, so for N rows, this adds up to O(N*M).

Combining these, the total time complexity is O(M + NM) = O(NM). Since you noted that M << N, this is nowhere near O(N²) — it's a much smaller complexity class (think of M as a small constant relative to N).

Optimizing with a set (as you mentioned) #

If you replace df2.var0.unique() with set(df2.var0), the time complexity gets even better:

1. set(df2.var0): Converting the column to a hash set takes O(M) time (we need to iterate through all M elements once).
2. The apply loop: Checking x in set(...) is a hash table lookup, which has an average O(1) time complexity (worst-case O(M) is extremely rare in practice). For N rows, this becomes O(N).

Total time complexity here is O(M + N) = O(N) (since M is negligible compared to N). This is a huge improvement over the original code.

A more Pandas-idiomatic alternative #

For even cleaner and often faster code, you can use Pandas' built-in isin() method instead of apply:

df1['var1'] = df1['var_ref'].isin(df2['var0']).astype(int)

Under the hood, Pandas optimizes isin() to use efficient lookup structures (similar to a set), so it has the same O(N) time complexity as the set-based approach, with less boilerplate code.

Final takeaway #

• Your original code has a time complexity of O(N*M), not O(N²).
• Switching to a set (or using isin()) drops the complexity to O(N) (dominated by N since M << N).

内容的提问来源于stack exchange，提问作者abdoulsn