The taint analysis technology is an effective method to detect the privacy data leakage of Android smart phones. However, the state-of-the-art tools of taint analysis for Android applications mainly focus on the accuracy with few of them addressing the importance of the efficiency and time cost. Actually, the high cost may cause problems such as timeouts or program crashes when the tools analyze some complex applications, which block them from wide usage. This study proposes a novel taint analysis approach based on the tainted value graph, which reduces the time cost and improves the efficiency. The tainted value graph is formalized to describe the tainted values and their relationships and the taint analysis and alias analysis are combined together without using the traditional data flow analysis framework. In addition, the taint flows are verified on the control flow graph to improve accuracy. The architecture, modules, and algorithmic details of the proposed tool FastDroid are also described in this paper. The tool is evaluated on three test suites:DroidBench-2.0, MalGenome, and 1517 apps randomly downloaded from Google Play. The experimental results show that, compared with the tool FlowDroid, FastDroid has a higher precision of 93.3% and a higher recall of 85.8% on DroidBench-2.0, and the time cost for analysis is less and more stable on all the test suites.