0
任何人都可以解釋下面描述的給定問題的方法如何在O（N）時間和O（1）空間中操作？以下方法的運行時間如何爲O（N）和空間複雜度爲O（1）？
問：鑑於2個有序陣列，找到共同的元素個數。數組長度相同，每個數組都有不同的元素。
採取以下2個陣列例如：
A: 13, 27, 35, 40, 49, 55, 59
B: 17, 35, 39, 40, 55, 58, 60
- 執行線性搜索在乙在B [0] = 17，在B停止[0] = A [0] = 13，開始17.未找到
- 不要在乙在B A [1] = 27開始的線性搜索[0] = 17，在B停止[1] = 35未找到
- 執行在B的線性搜索在B A [2] = 35開始[1] = 35，在B停止[1] = 35，發現
- 在b執行線性搜索在B A [3] = 40開始[2]39. =在停止B [3] = 40。發現
- 執行線性搜索在乙在B A [4] = 49開始[3] =中B 40停止[4] = 55，發現
我對我們正在做一個線性循環的部分感到困惑，該線性循環讓A的所有元素都已經產生O（N）時間，然後再次在B中進行線性搜索以找到元素。 B中的班輪搜索正在收集最後一個停止的地方。這不會使得給定方法O（N^2）的時間複雜性如何？如果不是，爲什麼？
@JimMischel不行，你只能從你在上一步離開的地方進行搜索。在這個過程結束時，你將訪問A和B中的每個元素一次，即O（n）。並且輸入數據的大小從未包含在算法的空間要求中。 – biziclop
啊，我讀得太快了。是的，這只是一種以不同方式表達的合併。 O（n），O（1）額外的空間。 –
@JimMischel：那麼最好的情況下O（N）和最壞的情況下O（N^2）？ – Milin